P7890 “MCOI-06” Lost Desire

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

Let positive integers $n, m$ be coprime, and let $k$ be an integer. Define the function $F(n, m, k)$ as follows: among the set of positive integers less than $\displaystyle m+n$, $\{1, 2, \cdots, m + n - 1\}$, consider all $m$-element subsets $S$ that satisfy $\displaystyle\sum_{x \in S} x \equiv k \pmod n$. Then $F(n, m, k)$ is the number of such subsets $S$. Now given positive integers $N, M, K$, compute the product of all $F(i, j, x)$ such that $1 \le i \le N$, $1 \le j \le M$, $1 \le x \le K$, and $i$ and $j$ are coprime. Since the result is very large, you only need to output the value modulo a given prime $p$. **Also, please pay attention to the impact of constant factors when implementing your program.**

**This problem has multiple test cases.** Each test point contains a total of $T$ test cases. The first line contains two positive integers $T, p$. The next $T$ lines each contain three positive integers $N, M, K$, separated by spaces.

For each test case, output one line with one integer, representing the required value (modulo $p$).

This problem uses bundled tests, divided into $5$ subtasks. + For Subtask 1 ~~(Tutorial)~~: + $T=1$. + $1 \leq N, M, K \leq 6$. + $p=10^9+7$. + For Subtask 2 ~~(PST 4.0)~~: + $T=1$. + $1 \leq N, M, K \leq 200$. + $p=10^9+7$. + For Subtask 3 ~~(PRS 7.5)~~: + $T=100$. + $1 \leq N, M, K \leq 1000$. + $p=10^9+7$. + For Subtask 4 ~~(FTR 9.8)~~: + $T=10^3$. + $1 \leq N, M, K \leq 10^5$. + $10^9 \le p \le 2 \times 10^9$. + For Subtask 5 ~~(BYD 11.0)~~: + $T=9999$. + $1 \leq N, M, K \le 5 \times 10^5$. + $10^9 \le p \le 2 \times 10^9$. The scores for Subtasks $1 \sim 5$ are $5, 7, 11, 17, 60$, respectively. In particular, suppose that in one test point the first $x$ queries are correct; then you get $\left\lfloor100\times\sqrt\dfrac{x}{T}\right\rfloor\%$ of the score of that test point. Your score for any Subtask is the minimum score among all test points in that Subtask. In particular, **any TLE gets $0$ points.** (There is no need to fill in the answers for test points that are not solved within the time limit; doing so may cause strange errors.) **Reminder again: please pay attention to the impact of constant factors when implementing your program.** --- Idea: Powerless Std&Data: w33z (Data was corrected on 2021.10.05). Subtask 4 was added by Prean, and Subtask 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 (wkywkywkywky). 2021.10.01 - 2022.02.26: 149 days, 3rd kill (NaNH2). Translated by ChatGPT 5