题目描述

白玉楼中，冥界的音乐会开始了。

Lusana ，Lyrica 和 Merlin 正在演奏。

东风谷 早苗 (Kochiya Sanae) 非常喜欢幽灵乐团的演奏，她想对她们的演奏评分。

因为幽灵乐团有 $3$ 个人，所以我们可以用 $3$ 个正整数 $A,B,C$ 来表示出乐团演奏的分数，她们的演奏分数可以表示为

$$ \prod{i=1}^{A}\prod{j=1}^{B}\prod_{k=1}^{C}\left(\frac{\mathrm{lcm}(i,j)}{\gcd(i,k)}\right)^{f(\text{type})} $$

因为音乐在不同的部分会有不同的听觉感受，所以 $\text{type}$ 会在 ${0,1,2}$ 中发生变化，其中：

$$ \begin{split} &f(0)=1 \ &f(1)=i \times j \times k \ &f(2)=\gcd (i,j,k) \end{split} $$

因为乐团的歌实在太好听了，导致分数特别高，所以她们的分数要对给定的正整数 $p$ 取模。

因为有很多歌曲要演奏，所以早苗给出了 $T$ 组询问。

输入格式

第一行两个正整数 $T$，$p$，含义详见题目描述。

接下来 $T$ 行，每行三个正整数 $A,B,C$ 表示每组询问。

输出格式

$T$ 行，每行三个正整数分别表示 $\text{type}= {0,1,2}$ 的时候给定式子的值

样例

input

3 998244853
1 1 1
2 2 2
3 3 3

output

1 1 1
16 4096 16
180292630 873575259 180292630

数据范围与提示

子任务

对于 $10\%$ 的数据：$1\leq A,B,C\leq 50$；

对于 $20\%$ 的数据：$1\leq A,B,C\leq 100 $；

另有 $10\%$ 的数据：$1\leq A,B,C\leq 100,A=B=C$；

对于 $60\%$ 的数据：$1\leq A,B,C\leq 10^3$；

对于 $100\%$ 的数据：$1\leq A,B,C\leq 10^5,10^7 \leq p \leq 1.05\times 10^9,T =70$，保证 $p$ 是一个质数。

早苗非常善良，就算你不知道所有的正确答案，她也会给你一些分数。

• 如果你的第一列是正确的，她将会给你这个测试点 $20\%$ 的分数。

• 如果你的第二列是正确的，她将会给你这个测试点 $40\%$ 的分数。

• 如果你的第三列是正确的，她将会给你这个测试点 $40\%$ 的分数。

所以就算你不知道答案是什么，也请你在你不知道的那些地方输出 $[0,2^{31})$ 内的整数，否则可能会造成不可预估的错误。

题目来源

迷途之家 2019 联赛 (MtOI2019) T5

出题人： CYJian