P3807 [Template] Lucas Theorem

This is a template problem.

Given integers $n, m, p$, compute $C_{n + m}^n \bmod p$. The input guarantees that $p$ is prime. Note: $C$ denotes the binomial coefficient.

This problem contains multiple test cases. The first line contains an integer $T$, the number of test cases. For each test case: One line with three integers $n, m, p$.

For each test case, output one line with one integer, the required value.

For $100\%$ of the testdata, $1 \leq n, m, p \leq 10^5$, $1 \leq T \leq 10$. Translated by ChatGPT 5