Background

頰滴る　紅い涙

不安定な視界の中

差し出した手を取れたら

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

哭いて…

激しく 燃やした 黒い感情

届かぬ この手に

Cry 闇の中で

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

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

Netease Cloud Music trial listening link for this song

Problem Description

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.

Input Format

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.

Output Format

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

3 1926195307
2 3 3
3 3 3
5 6 1

8
64
363031200

Hint

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