题目背景

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

Lunasa，Lyrica和Merlin正在演奏。

题目描述

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

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

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

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

$$f(0)=1$$ $$f(1)=i \times j \times k$$ $$f(2)=\gcd(i,j,k)$$

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

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

输入格式

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

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

输出格式

$T$ 行，每行三个正整数分别表示 $type=0/1/2$ 的时候给定式子的值。

3 998244853
1 1 1
2 2 2
3 3 3

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\ \ \ \ p\in \{ prime\} \ \ \ \ T =70 $$

---

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

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

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

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

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

题目来源

迷途之家2019联赛(MtOI2019) T5

出题人：CYJian