Description

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.

Input Format

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$.

Output Format

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

2
1 2 5
2 1 5

3
3

Hint

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

Translated by ChatGPT 5