Interesting Permutations

Time limit5sMemory limit512 MB

Summary

Count permutations of 1..n whose first i elements are pairwise coprime, for every i, modulo m, stopping at the first impossible i.

Level: Medium7 of 10
Topics: Dynamic programming, Number theory, Combinatorics, Bit manipulation
Solved: No attempts yet

Problem

Vasya studies permutations of length $n$ : sequences of $n$ integers such that every integer from $1$ to $n$ occurs in the sequence exactly once. Vasya says a permutation is $k$ -interesting if its first $k$ elements are pairwise coprime. By this definition, if a permutation is $i$ -interesting, it is also $(i - 1)$ -interesting.

Now Vasya wants to find the number of $i$ -interesting permutations for all $i$ from $1$ to $n$ . If there is no $i$ -interesting permutation for a given $i$ , Vasya won't bother calculating for larger values of $i$ . For example, as numbers $2$ and $4$ are not coprime, there is no $5$ -interesting permutation of length $5$ .

Vasya does not like huge integers, so he calculates the number of permutations modulo a given integer $m$ . Help him do it.

Input

The first line contains two integers $n$ and $m$ ( $1 \le n \le 100$ , $1 \le m \le 10^9$ ).

Output

Print $k$ lines, where $k$ is the maximum number such that there is at least one $k$ -interesting permutation of length $n$ . On the $i$ -th line, print the remainder modulo $m$ of the number of $i$ -interesting permutations of length $n$ .

Examples2

Example 1
Input
```
5 239
```
Expected output
```
120
108
84
48
```
Example 2
Input
```
4 8
```
Expected output
```
0
4
4
```