Перестановкой размера \(n\) называется массив \(\langle a_1, a_2, \ldots, a_n \rangle\) различных чисел от \(1\) до \(n\). Каждое число в перестановке встречается ровно один раз.
Сеня называет красотой перестановки \(\langle a_1, a_2, \ldots, a_n \rangle\) число \((a_1a_2 + a_2a_3 + \ldots + a_{n-1}a_n)\). Он хочет посчитать количество перестановок, красота которых делится на \(k\).
Даны числа \(n\) и \(k\), найдите количество перестановок размера \(n\), красота которых делится на \(k\).
Например, для \(n = 3\) существует \(6\) перестановок. Рассмотрим все эти перестановки и их красоту.
| \(\langle 1, 2, 3\rangle\) |
\(1\cdot2 + 2\cdot3 = 8\) |
| \(\langle 1, 3, 2\rangle\) |
\(1\cdot3 + 3\cdot2 = 9\) |
| \(\langle 2, 1, 3\rangle\) |
\(2\cdot1 + 1\cdot3 = 5\) |
| \(\langle 2, 3, 1\rangle\) |
\(2\cdot3 + 3\cdot1 = 9\) |
| \(\langle 3, 1, 2\rangle\) |
\(3\cdot1 + 1\cdot2 = 5\) |
| \(\langle 3, 2, 1\rangle\) |
\(3\cdot2 + 2\cdot1 = 8\) |
Формат входных данных
Входные данные содержат два целых числа: \(n\) и \(k\) (\(1 \le n \le 10\), \(2 \le k \le 1000\)).
Формат выходных данных
Выведите одно целое число: количество перестановок размера \(n\), красота которых делится на \(k\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 2
|
2
|