「MCOI-06」Lost Desire

頰滴る　紅い涙 不安定な視界の中 差し出した手を取れたら あぁ…そんな世界を夢みた ------- 哭いて… 激しく 燃やした 黒い感情 届かぬ この手に Cry 闇の中で 最果てから 光へ手を翳して 揺らいだ想いさえも 闇の奥底へ堕ちてく [网易云本曲试听链接](https://music.163.com/song?id=1809745288&userid=1399272307)

设正整数 $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).