Fair Problemset

문제

This problem adopts exactly the same definition of Fair Problemset as Problem M, “Triple Fairness”.

ICPC is a team competition. Each team has three members. At the beginning of a contest, most teams divide the $3n3n$ problem evenly. They use one of two common methods to distribute problems:

1. Sequential Distribution: Each member takes a contiguous block of $nn$ problems from the set of $3n3n$ problems. Specifically, the first member takes problems $1,\cdots ,n1,\; \backslash cdots\; ,\; n$, the second member takes problems $n+1,\cdots ,2nn\; +\; 1,\; \backslash cdots\; ,\; 2n$, and the third member takes problems $2n+1,\cdots ,3n2n\; +\; 1,\; \backslash cdots\; ,\; 3n$.
2. Jump Distribution: Each member takes problems with indices that have the same remainder when divided by $33$ from the set of $3n3n$ problems. Specifically, the first member takes problems 1, 4, 7, \cdots , 3n − 2, the second member takes problems 2, 5, 8, \cdots , 3n − 1, and the third member takes problems $3,6,9,\cdots ,3n3,\; 6,\; 9,\; \backslash cdots\; ,\; 3n$.

The ICPC Seoul Regional Contest Scientific Committee must prepare a problemset consisting of $3n3n$ problems. The difficulty of each problem is represented by an integer from $11$ to $nn$, inclusive. For each difficulty, there are exactly three problems with that difficulty. Thus, the arrangement of difficulties in the problemset can be viewed as a difficulty sequence of length $3n3n$ containing three problems of each of the $nn$ difficulty levels.

To prevent any advantage or disadvantage for a team based on their chosen problem distribution method, the ICPC Seoul Regional Contest Scientific Committee has defined a standard called a Fair Problemset. A difficulty sequence of length $3n3n$ is called a Fair Problemset if it satisfies both of the following conditions:

1. Sequential Distribution Fairness: When using Sequential Distribution, for every difficulty level $ii$ (1 ≤ i ≤ n), each of the three members receives exactly one problem with difficulty $ii$.
2. Jump Distribution Fairness: When using Jump Distribution, for every difficulty level $ii$ (1 ≤ i ≤ n), each of the three members receives exactly one problem with difficulty $ii$.

In other words, regardless of which of the two methods is chosen, each team member must be assigned exactly one problem for each difficulty level from $11$ to $nn$, inclusive.

Given a positive integer $kk$, write a program to find the number of Fair Problemset sequences of length $3n3n$ for each $n=1,2,\cdots ,kn\; =\; 1,\; 2,\; \backslash cdots\; ,\; k$.

입력

Your program is to read from standard input. The input consists of exactly one line. The line contains two integers, $kk$ and $mm$ (1 ≤ k ≤ 10^6; ; $mm$ is a prime number).

출력

Your program is to write to standard output. You should print exactly $kk$ lines. On the $nn$-th line (1 ≤ n ≤ k), print the number of Fair Problemset sequences of length $3n3n$, modulo $mm$.

힌트

Explanation of Sample Input 2:

Here are $1212$ Fair Problemset sequences of length $9(=3\times 39\; (=\; 3\; \backslash times\; 3$).

1. $11$ $22$ $33$ $22$ $33$ $11$ $33$ $11$ $22$
2. $11$ $22$ $33$ $33$ $11$ $22$ $22$ $33$ $11$
3. $11$ $33$ $22$ $22$ $11$ $33$ $33$ $22$ $11$
4. $11$ $33$ $22$ $33$ $22$ $11$ $22$ $11$ $33$
5. $22$ $11$ $33$ $11$ $33$ $22$ $33$ $22$ $11$
6. $22$ $11$ $33$ $33$ $22$ $11$ $11$ $33$ $22$
7. $22$ $33$ $11$ $11$ $22$ $33$ $33$ $11$ $22$
8. $22$ $33$ $11$ $33$ $11$ $22$ $11$ $22$ $33$
9. $33$ $11$ $22$ $11$ $22$ $33$ $22$ $33$ $11$
10. $33$ $11$ $22$ $22$ $33$ $11$ $11$ $22$ $33$
11. $33$ $22$ $11$ $11$ $33$ $22$ $22$ $11$ $33$
12. $33$ $22$ $11$ $22$ $11$ $33$ $11$ $33$ $22$

2 993244853

1
2

3 998244353

1
2
12