Description

After class, Lulu, Huahua, and Xuanxuan set up a “seesaw” on the desk using a regular triangular prism teaching aid and a ruler.

The structure of this “seesaw” is as follows: at the bottom is a regular triangular prism with one of its lateral faces parallel to the ground, and on top lies a ruler. Several identical erasers are placed on the ruler. The ruler has $2n+1$ equally spaced tick marks; the $(n+1)$-th tick is exactly at the center of the ruler and exactly coincides with the edge of the regular triangular prism that is not on the desk.

Lulu notices that the “seesaw” is unbalanced (the ruler is not parallel to the ground). So she adds a few more erasers and moves some erasers so that each of the $2n+1$ tick marks on the ruler has exactly one eraser of the same mass. The “seesaw” becomes balanced, and Lulu is happy.

Huahua thinks this is too boring, so she randomly removes $k$ erasers from the ruler. To her surprise, the ruler remains balanced!

Xuanxuan is a thoughtful child, so she is not surprised that the ruler remains balanced, as this is merely a coincidence. What interests her is: in how many ways can Huahua remove $k$ erasers so that the ruler remains balanced? Of course, to simplify the problem, she has to make some sacrifices—assume all erasers are point masses with equal mass. Even so, she cannot compute this number. After school, she brings this problem to her older brother/sister—the student council president of Hibarigasaki Academy, that is, you. Since the answer may be too large, you only need to tell her the value modulo $p$.

Input Format

The first line contains a positive integer $T$ (the number of times Xuanxuan asks you).

Each of the next $T$ lines contains three positive integers $n$, $k$, and $p$.

Output Format

Output $T$ lines, each containing one positive integer, the answer for the corresponding query.

10
6 5 10000  
4 1 10000 
9 6 10000 
4 6 10000 
5 1 10000 
8318 10 9973 
9862 9 9973 
8234 9 9973 
9424 9 9973 
9324 9 9973

73
1
920
8
1
4421
2565
0
446
2549

Hint

• 10% of the testdata satisfy $n \le 10$.
• 30% of the testdata satisfy $n \le 50$.
• 50% of the testdata satisfy $n \le 1000$.
• Additionally, 10% of the testdata satisfy $k = 3$.
• Additionally, 10% of the testdata satisfy $p = 2$.
• 100% of the testdata satisfy $T \le 20$, $1 \le n \le 10000$, $1 \le k \le 10$, $2 \le p \le 10000$, and $k \le 2n+1$.

Translated by ChatGPT 5