[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$ 的时候给定式子的值。

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