题目背景

頰滴る　紅い涙

不安定な視界の中

差し出した手を取れたら

あぁ…そんな世界を夢みた

---

哭いて…

激しく 燃やした 黒い感情

届かぬ この手に

Cry 闇の中で

最果てから 光へ手を翳して

揺らいだ想いさえも 闇の奥底へ堕ちてく

网易云本曲试听链接

题目描述

设正整数 $n, m$ 互质，$k$ 为整数，定义函数 $F(n, m, k)$ 为小于 $\displaystyle m+n$ 的正整数集合 $\{1, 2, \cdots, m + n - 1\}$ 中，所有满足 $\displaystyle\sum_{x \in S} x \equiv k \pmod n$ 的 $m$ 元子集 $S$ 的个数。

现给定正整数 $N, M, K$，求所有 $F(i,j,x)$ 之积，使得 $1\le i\le N$，$1\le j\le M$，$1\le x\le K$，并且 $i$ 与 $j$ 互质。

由于结果很大，所以你只需要求出结果对特定素数 $p$ 取模的值。

同时请注意实现程序时常数因子带来的影响。

输入格式

本题多测。 每个测试点共有 $T$ 组数据。

第一行两个正整数 $T,p$ 。

接下来 $T$ 行，每行三个正整数 $N, M, K$，由空格分开。

输出格式

对于每组数据：一行，一个整数，表示所求的值（对 $p$ 取模）。

3 1926195307
2 3 3
3 3 3
5 6 1

8
64
363031200

提示

本题采用捆绑测试，分 $5$ 个 Subtask 。

• 对于 Subtask 1 (Tutorial)：
  • $T=1$
  • $1\leq N,M,K\leq 6$
  • $p=10^9+7$。
• 对于 Subtask 2 (PST 4.0)：
  • $T=1$
  • $1\leq N,M,K\leq200$
  • $p=10^9+7$。
• 对于 Subtask 3 (PRS 7.5)：
  • $T=100$
  • $1\leq N,M,K\leq 1000$
  • $p=10^9+7$。
• 对于 Subtask 4 (FTR 9.8)：
  • $T=10^3$
  • $1 \leq N,M,K\le 10^5$
  • $10^9\le p\le2\times10^9$。
• 对于 Subtask 5 (BYD 11.0)：
  • $T=9999$
  • $1 \leq N,M,K\le 5\times10^5$
  • $10^9\le p\le2\times10^9$。

Subtask $1\sim5$ 的分值分别为 $5,7,11,17,60$ 。

特别的，假设您在一个测试点中前 $x$ 个询问正确，则您得该测试点的分值的 $\left\lfloor100\times\sqrt\dfrac{x}{T}\right\rfloor\%$ 分。您在任何一个 Subtask 的得分则为对应 Subtask 中所有测试点得分的最小值。

特别的，TLE 一律不得分。（无需补满未在时间范围内解决的测试点的答案，会导致奇怪的错误。）

再次提醒注意实现程序时常数因子带来的影响。

---

Idea: Powerless Std&Data: w33z （Data was corrected on 2021.10.05）

Sub4 added by Prean, Sub 5 by w33z.

This problem was added on 2021.10.01. Thanks for their help.

2021.10.01 - 2021.12.07 : 68 days 1st kill (Leasier).

2021.10.01 - 2022.01.21 : 113 days 2nd kill (wkywkywky).

2021.10.01 - 2022.02.26 : 149 days 3rd kill (NaNH2).