This is the hard version of the problem. The difference between the two versions is the definition of deterministic max-heap, time limit, and constraints on $n$ and $t$. You can make hacks only if both versions of the problem are solved.

Consider a perfect binary tree with size $2^n - 1$, with nodes numbered from $1$ to $2^n-1$ and rooted at $1$. For each vertex $v$ ($1 \le v \le 2^{n - 1} - 1$), vertex $2v$ is its left child and vertex $2v + 1$ is its right child. Each node $v$ also has a value $a_v$ assigned to it.

Define the operation $\mathrm{pop}$ as follows:

1. initialize variable $v$ as $1$;
2. repeat the following process until vertex $v$ is a leaf (i.e. until $2^{n - 1} \le v \le 2^n - 1$); among the children of $v$, choose the one with the larger value on it and denote such vertex as $x$; if the values on them are equal (i.e. $a_{2v} = a_{2v + 1}$), you can choose any of them; assign $a_x$ to $a_v$ (i.e. $a_v := a_x$); assign $x$ to $v$ (i.e. $v := x$);
3. assign $-1$ to $a_v$ (i.e. $a_v := -1$).

Then we say the $\mathrm{pop}$ operation is deterministic if there is a unique way to do such operation. In other words, $a_{2v} \neq a_{2v + 1}$ would hold whenever choosing between them.

A binary tree is called a max-heap if for every vertex $v$ ($1 \le v \le 2^{n - 1} - 1$), both $a_v \ge a_{2v}$ and $a_v \ge a_{2v + 1}$ hold.

A max-heap is deterministic if the $\mathrm{pop}$ operation is deterministic to the heap when we do it for the first and the second time.

Initially, $a_v := 0$ for every vertex $v$ ($1 \le v \le 2^n - 1$), and your goal is to count the number of different deterministic max-heaps produced by applying the following operation $\mathrm{add}$ exactly $k$ times:

• Choose an integer $v$ ($1 \le v \le 2^n - 1$) and, for every vertex $x$ on the path between $1$ and $v$, add $1$ to $a_x$.

Two heaps are considered different if there is a node which has different values in the heaps.

Since the answer might be large, print it modulo $p$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 50$). The description of the test cases follows.

The first line of each test case contains three integers $n, k, p$ ($2 \le n \le 100$, $1 \le k \le 500$, $10^8 \le p \le 10^9$, $p$ is a prime).

It is guaranteed that the sum of $n$ does not exceed $100$ and the sum of $k$ over all test cases does not exceed $500$.

Output

For each test case, output a single line containing an integer: the number of different deterministic max-heaps produced by applying the aforementioned operation $\mathrm{add}$ exactly $k$ times, modulo $p$.

见题面 Input 部分

见题面 Output 部分

For the first testcase, if we choose $v = 1$ and do the operation, we would have $a = [1, 0, 0]$, and since $a_2 = a_3$, we can choose either of them when doing the first $\mathrm{pop}$ operation, so such heap is not a deterministic max-heap.

And if we choose $v = 2$, we would have $a = [1, 1, 0]$, during the first $\mathrm{pop}$, the following would happen:

• initialize $v$ as $1$
• since $a_{2v} > a_{2v + 1}$, choose $2v$ as $x$, then $x = 2$
• assign $a_x$ to $a_v$, then $a = [1, 1, 0]$
• assign $x$ to $v$, then $v = 2$
• since $v$ is a leaf, assign $-1$ to $a_v$, then $a = [1, -1, 0]$

And during the second $\mathrm{pop}$, the following would happen:

• initialize $v$ as $1$
• since $a_{2v} < a_{2v + 1}$, choose $2v + 1$ as $x$, then $x = 3$
• assign $a_x$ to $a_v$, then $a = [0, -1, 0]$
• assign $x$ to $v$, then $v = 3$
• since $v$ is a leaf, assign $-1$ to $a_v$, then $a = [0, -1, -1]$

Since both the first and the second $\mathrm{pop}$ operation are deterministic, this is a deterministic max-heap. Also, if we choose $v = 3$, $a$ would be a deterministic max-heap, so the answer is $2$.