#214772. [ICPC 2025 Seoul R] 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 problem evenly. They use one of two common methods to distribute problems:

1. Sequential Distribution: Each member takes a contiguous block of problems from the set of problems. Specifically, the first member takes problems , the second member takes problems , and the third member takes problems .
2. Jump Distribution: Each member takes problems with indices that have the same remainder when divided by 3 from the set of problems. Specifically, the first member takes problems , the second member takes problems , and the third member takes problems .

The ICPC Seoul Regional Contest Scientific Committee must prepare a problemset consisting of problems. The difficulty of each problem is represented by an integer from 1 to , 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 containing three problems of each of the 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 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 (), each of the three members receives exactly one problem with difficulty .
2. Jump Distribution Fairness: When using Jump Distribution, for every difficulty level (), each of the three members receives exactly one problem with difficulty .

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 , inclusive.

Given a positive integer , write a program to find the number of Fair Problemset sequences of length for each .

Your program is to read from standard input. The input consists of exactly one line. The line contains two integers, and (; ; is a prime number).

Your program is to write to standard output. You should print exactly lines. On the -th line (), print the number of Fair Problemset sequences of length , modulo .

样例输入 1

2 993244853

样例输出 1

1
2

样例输入 2

3 998244353

样例输出 2

1
2
12

Here are Fair Problemset sequences of length ()

i.    1 2 3 2 3 1 3 1 2
ii.   1 2 3 3 1 2 2 3 1
iii.  1 3 2 2 1 3 3 2 1
iv.   1 3 2 3 2 1 2 1 3
v.    2 1 3 1 3 2 3 2 1
vi.   2 1 3 3 2 1 1 3 2
vii.  2 3 1 1 2 3 3 1 2
viii. 2 3 1 3 1 2 1 2 3
ix.   3 1 2 1 2 3 2 3 1
x.    3 1 2 2 3 1 1 2 3
xi.   3 2 1 1 3 2 2 1 3
xii.  3 2 1 2 1 3 1 3 2