Beautiful Permutations

Interview

Time limit1sMemory limit1024 MB

Summary

Given n and k, count the permutations of 1 to n whose sum of adjacent products is divisible by k.

Level: Medium5 of 10
Topics: Dynamic programming, Bit manipulation, Brute force
Solved: No attempts yet

Statement

A permutation of size $n$ is an array $\langle a_1, a_2, \ldots, a_n \rangle$ of distinct integers from $1$ to $n$ . Each number appears in the permutation exactly once.

Senya calls the beauty of a permutation $\langle a_1, a_2, \ldots, a_n \rangle$ the value $a_1a_2 + a_2a_3 + \ldots + a_{n-1}a_n$ . He wants to count the permutations whose beauty is divisible by $k$ .

Given $n$ and $k$ , find the number of permutations of size $n$ whose beauty is divisible by $k$ .

Input

Two integers $n$ and $k$ are given ( $1 \le n \le 10$ , $2 \le k \le 1000$ ).

Output

Print one integer: the number of permutations of size $n$ whose beauty is divisible by $k$ .

Examples1

Example 1
Input
```
3 2
```
Expected output
```
2
```