[MtOI2019]幽灵乐团 / 莫比乌斯反演基础练习题

题目背景

白玉楼中,冥界的音乐会开始了。 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\}$ 中发生变化,其中: $$\begin{aligned} f(0)&=1 \cr f(1)&=i \times j \times k \cr f(2)&=\gcd(i,j,k) \end{aligned}$$ 因为乐团的歌实在太好听了,导致分数特别高,所以她们的分数要对给定的正整数 $p$ 取模。 因为有很多歌曲要演奏,所以早苗给出了 $T$ 组询问。

输入输出格式

输入格式


第一行两个正整数 $T$,$p$,含义详见题目描述。 接下来 $T$ 行,每行三个正整数 $A,B,C$ 表示每组询问。

输出格式


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

输入输出样例

输入样例 #1

3 998244853
1 1 1
2 2 2
3 3 3

输出样例 #1

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联赛](https://www.luogu.org/contest/20135)(MtOI2019) T5 出题人:CYJian