#1325. 「MtOI2019」幽灵乐团

内存限制:256 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: Quank123Wip

题目描述

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

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(type)}

因为音乐在不同的部分会有不同的听觉感受,所以 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 行,每行三个正整数分别表示 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,T =70 ,保证 p 是一个质数。


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

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

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

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

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

题目来源

迷途之家 2019 联赛 (MtOI2019) T5

出题人: CYJian