Deterministic Heap (Easy Version)
Contest: Codeforces Round 967 (Div. 2)
Difficulty rating: 2400
Tags: combinatorics, dp, math, trees

This is the easy 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 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 format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 500$$$). The description of the test cases follows.

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

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

Output format:
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$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Note:
For the first testcase, there is only one way to generate $$$a$$$, and such sequence is a deterministic max-heap, so the answer is $$$1$$$.

For the second 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]$$$

Since the first $$$\mathrm{pop}$$$ operation is 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$$$.

Example input:
7
1 13 998244353
2 1 998244353
3 2 998244853
3 3 998244353
3 4 100000037
4 2 100000039
4 3 100000037

Example output:
1
2
12
52
124
32
304

Example input:
1
500 500 100000007

Example output:
76297230

Editorial:
Consider properties of the result sequence:
Since there may be multiple ways to apply operations to make the same heap, let's consider the decision version of the problem instead of counting the operation sequence directly. That is, "Given a sequence $$$a$$$ resulting from $$$k$$$ operations, check whether such $$$a$$$ is a deterministic max-heap.", and try to figure out what properties are needed.
Rephrase of problem:
Let $$$v = 2^{n - 1}$$$ be the only leaf such that after popping one element from the top, every element on the path between $$$1$$$ and $$$v$$$ would be moved upward, then the condition of a deterministic max-heap can be rephrased as follows:
1. $$$a_1 = k$$$
2. $$$a_{v} \ge a_{2v} + a_{2v + 1}$$$, for any $$$v$$$ ($$$1 \le v < 2^{n - 1}$$$)
3. $$$a_{2\cdot 2^k} > a_{2 \cdot 2^k + 1}$$$, for any $$$k$$$ ($$$0 \le k \le n - 2$$$)
So we can see that for any $$$k$$$ ($$$0 \le k \le n - 2$$$), the number of operations done in the subtree of $$$2\cdot 2^k$$$ should be greater than the number of operations done in the subtree of $$$2 \cdot 2^k + 1$$$, and we don't care much about how these operations distribute in the subtree of $$$2 \cdot 2^k + 1$$$ as long as 3. holds. Let's call such subtree "uncritical".
Apply counting:
For any uncritical subtree with size $$$sz$$$, if we do $$$x$$$ operations under it, there are $$$\binom{x + (sz - 1)}{x}$$$ ways to do so.
Now we can use dp to consider all valid $$$a$$$ we can get by enumerating the number of operation done on each vertex on the path from $$$1$$$ to $$$2^{n - 1}$$$ and all uncritical subtree.
Let $$$dp[i][j]$$$ be the number of different $$$a$$$ we can get by $$$j$$$ operations on the subtree with size $$$2^i - 1$$$, then we have
base case: $$$dp[1][j] = 1, \forall j \in [0, k]$$$
transition: $$$dp[i + 1][l] \text{ += } dp[i][j] \times \binom{x + (2^i - 2)}{x} ,\forall x \in [0, j), l \in [j + x, k]$$$
using prefix sum, we can optimize the above dp to $$$O(nk^2)$$$, and the number of deterministic max-heap where vertex $$$2^{n - 1}$$$ would be pulled up is $$$dp[n][k]$$$.
Observe symmetry:
Finally, observe you can swap some vertex's left and right subtrees to obtain a deterministic max-heap where vertex $$$v'$$$ would be pulled up for any $$$(2^{n - 1} \le v' < 2^{n})$$$, which implies the number of deterministic max-heap where $$$v'$$$ would be pulled are equal for all possible $$$v'$$$, the final answer we want would be $$$dp[n][k] \times 2^{n - 1}$$$.