| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 8 초 | 2048 MB | 52 | 27 | 17 | 45.946% |
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 $3n$ problem evenly. They use one of two common methods to distribute problems:
The ICPC Seoul Regional Contest Scientific Committee must prepare a problemset consisting of $3n$ problems. The difficulty of each problem is represented by an integer from $1$ to $n$, 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 $3n$ containing three problems of each of the $n$ 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 $3n$ is called a Fair Problemset if it satisfies both of the following conditions:
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 $1$ to $n$, inclusive.
Given a positive integer $k$, write a program to find the number of Fair Problemset sequences of length $3n$ for each $n = 1, 2, \cdots , k$.
Your program is to read from standard input. The input consists of exactly one line. The line contains two integers, $k$ and $m$ ($1 ≤ k ≤ 10^6$; $10^8 < m < 10^9$; $m$ is a prime number).
Your program is to write to standard output. You should print exactly $k$ lines. On the $n$-th line ($1 ≤ n ≤ k$), print the number of Fair Problemset sequences of length $3n$, modulo $m$.
2 993244853
1 2
3 998244353
1 2 12
Explanation of Sample Input 2:
Here are $12$ Fair Problemset sequences of length $9 (= 3 \times 3$).
ICPC > Regionals > Asia Pacific > Korea > 2025 ICPC Asia Seoul Regional H번