Fair Problemset - 問題

本题采用了与 M 题“三重公平性”（Triple Fairness）完全相同的“公平题集”（Fair Problemset）定义。

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

顺序分配（Sequential Distribution）：每位成员从 $3n$ 道题目中取走一个长度为 $n$ 的连续区间。具体来说，第一位成员取走第 $1, \dots, n$ 题，第二位成员取走第 $n + 1, \dots, 2n$ 题，第三位成员取走第 $2n + 1, \dots, 3n$ 题。
跳跃分配（Jump Distribution）：每位成员取走 $3n$ 道题目中下标除以 3 余数相同的题目。具体来说，第一位成员取走第 $1, 4, 7, \dots, 3n - 2$ 题，第二位成员取走第 $2, 5, 8, \dots, 3n - 1$ 题，第三位成员取走第 $3, 6, 9, \dots, 3n$ 题。

ICPC 首尔区域赛科学委员会必须准备一套包含 $3n$ 道题目的题集。每道题的难度用 $1$ 到 $n$ 之间的整数表示。对于每个难度等级，恰好有三道题目。因此，题集中的难度排列可以看作是一个长度为 $3n$ 的难度序列，其中包含 $n$ 个难度等级，每个等级各出现三次。

为了防止队伍因选择的题目分配方式而获得任何优势或劣势，ICPC 首尔区域赛科学委员会定义了一个标准，称为“公平题集”。如果一个长度为 $3n$ 的难度序列满足以下两个条件，则称其为公平题集：

顺序分配公平性：当使用顺序分配时，对于每个难度等级 $i$ ($1 \le i \le n$)，三位成员中的每一位都恰好获得一道难度为 $i$ 的题目。
跳跃分配公平性：当使用跳跃分配时，对于每个难度等级 $i$ ($1 \le i \le n$)，三位成员中的每一位都恰好获得一道难度为 $i$ 的题目。

换句话说，无论选择哪种分配方法，每位团队成员都必须被分配到 $1$ 到 $n$ 每个难度等级的题目各一道。

给定一个正整数 $k$，编写一个程序，计算对于每个 $n = 1, 2, \dots, k$，长度为 $3n$ 的公平题集序列的数量。

程序从标准输入读取数据。输入仅包含一行，包含两个整数 $k$ 和 $m$ ($1 \le k \le 10^6$; $10^8 < m < 10^9$; $m$ 是一个质数)。

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

2 993244853

1
2

3 998244353

1
2
12

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

QOJ.ac