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