E1. Deterministic Heap (Easy Version)time limit per test3 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputThis 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: initialize variable $$$v$$$ as $$$1$$$; 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$$$); 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$$$.InputEach 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$$$.OutputFor 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$$$.ExamplesInput71 13 9982443532 1 9982443533 2 9982448533 3 9982443533 4 1000000374 2 1000000394 3 100000037Output1
2
12
52
124
32
304
Input1500 500 100000007Output76297230
Input687 63 10000003777 77 100000039100 200 998244353200 100 99824435332 59 9982448531 1 998244353Output26831232
94573603
37147649
847564946
727060898
1
NoteFor 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$$$.