Description

本题采纳与 M 题 "Triple Fairness" 完全相同的 公平试题集 定义。

ICPC 是一项团队竞赛。每个团队有三名成员。在比赛开始时，大多数团队会将 $3n$ 道题平均分配。他们通常使用以下两种常见方法来分配题目：

1. 顺序分配：每位成员从 $3n$ 道题中取一个连续的 $n$ 道题块。具体来说，第一名成员取题目 $1, \cdots, n$，第二名成员取题目 $n+1, \cdots, 2n$，第三名成员取题目 $2n+1, \cdots, 3n$。
2. 跳跃分配：每位成员从 $3n$ 道题中取索引除以 $3$ 余数相同的题目。具体来说，第一名成员取题目 $1, 4, 7, \cdots, 3n-2$，第二名成员取题目 $2, 5, 8, \cdots, 3n-1$，第三名成员取题目 $3, 6, 9, \cdots, 3n$。

ICPC 首尔赛区科学委员会需要准备一个由 $3n$ 道题组成的试题集。每道题的难度用一个从 $1$ 到 $n$（含）的整数表示。对于每种难度，恰好有三道题具有该难度。因此，试题集中的难度排列可以看作一个长度为 $3n$ 的难度序列，其中包含每种 $n$ 个难度级别的三道题。

为了防止任何团队因选择的问题分配方法而获得优势或处于劣势，ICPC 首尔赛区科学委员会定义了一个称为 公平试题集 的标准。一个长度为 $3n$ 的难度序列被称为公平试题集，当且仅当它同时满足以下两个条件：

1. 顺序分配公平性：当使用顺序分配时，对于每个难度级别 $i$ ($1 \le i \le n$)，三名成员每人恰好收到一道难度为 $i$ 的题。
2. 跳跃分配公平性：当使用跳跃分配时，对于每个难度级别 $i$ ($1 \le i \le n$)，三名成员每人恰好收到一道难度为 $i$ 的题。

换句话说，无论选择两种方法中的哪一种，每个团队成员都必须被分配到恰好一道难度为 $1$ 到 $n$（含）中每个级别的题目。

给定一个正整数 $k$，请编写一个程序，对每个 $n = 1, 2, \cdots, k$，找出长度为 $3n$ 的公平试题集序列的数量。

Input Format

你的程序需要从标准输入读取数据。输入恰好包含一行。该行包含两个整数 $k$ 和 $m$ ($1 \le k \le 10^6$； $10^8 < m < 10^9$； $m$ 是一个质数)。

Output Format

你的程序需要向标准输出写入数据。你应该恰好输出 $k$ 行。在第 $n$ 行 ($1 \le n \le k$) 上，输出长度为 $3n$ 的公平试题集序列的数量，结果对 $m$ 取模。

2 993244853

1
2

3 998244353

1
2
12

Hint

以下是长度为 $9$ ($= 3 \times 3$) 的 $12$ 个公平试题集序列：

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

翻译由 DeepSeek V3 完成