题目翻译

---

E1. 确定性堆（简单版）

每测试点时间限制：3 秒
内存限制：512 MB

这是问题的简单版本。两个版本的区别在于确定性最大堆的定义、时间限制以及 $n$ 和 $t$ 的约束。
只有当两个版本都通过时，你才能进行 hack。

---

题目描述

考虑一棵大小为 $2^n - 1$ 的完美二叉树，节点编号为 $1$ 到 $2^n - 1$，根节点为 $1$。
对于每个节点 $v$（$1 \le v \le 2^{n-1} - 1$），其左子节点为 $2v$，右子节点为 $2v + 1$。
每个节点 $v$ 有一个值 $a_v$ 与之对应。

定义 pop 操作如下：

1. 初始化变量 $v = 1$；
2. 重复以下过程直到 $v$ 为叶子节点（即 $2^{n-1} \le v \le 2^n - 1$）：
   • 在 $v$ 的子节点中，选择值较大的节点，记为 $x$；若两个子节点值相等（$a_{2v} = a_{2v+1}$），则可任意选择其一；
   • 将 $a_x$ 赋值给 $a_v$（即 $a_v := a_x$）；
   • 将 $x$ 赋值给 $v$（即 $v := x$）；
3. 将 $a_v$ 赋值为 $-1$（即 $a_v := -1$）。

如果该操作只有唯一的方法执行，则称这次 pop 操作是确定性的。
换句话说，在选择子节点时，必须满足 $a_{2v} \neq a_{2v+1}$。

---

一棵二叉树称为 最大堆（max-heap），如果对每个节点 $v$（$1 \le v \le 2^{n-1} - 1$），都有 $a_v \ge a_{2v}$ 且 $a_v \ge a_{2v+1}$。

一个最大堆称为确定性的，如果在第一次对它执行 pop 操作时，该操作是确定性的。

---

初始时，每个节点 $v$ 的值为 $a_v := 0$。
你的目标是：计算通过恰好执行 $k$ 次如下 add 操作能得到的不同确定性最大堆的数量。

• add 操作：选择一个整数 $v$（$1 \le v \le 2^n - 1$），对从 $1$ 到 $v$ 路径上的每个节点 $x$，将 $a_x$ 增加 $1$。

两个堆被认为是不同的，如果存在某个节点的值在两个堆中不同。

由于答案可能很大，请输出其对 $p$ 取模的结果。

---

输入格式

每个测试包含多个测试用例。
第一行包含一个整数 $t$（$1 \le t \le 500$），表示测试用例数。

接下来每个测试用例一行，包含三个整数 $n, k, p$：

• $1 \le n, k \le 500$，
• $10^8 \le p \le 10^9$，且 $p$ 是素数。

保证所有测试用例的 $n$ 之和 $\le 500$，且 $k$ 之和 $\le 500$。

---

输出格式

对于每个测试用例，输出一行一个整数：通过恰好 $k$ 次 add 操作能得到的不同确定性最大堆的数量，对 $p$ 取模。

---

示例

示例输入 1

7
1 13 998244353
2 1 998244353
3 2 998244853
3 3 998244353
3 4 100000037
4 2 100000039
4 3 100000037

示例输出 1

1
2
12
52
124
32
304

---

示例输入 2

1
500 500 100000007

示例输出 2

76297230

---

示例输入 3

6
87 63 100000037
77 77 100000039
100 200 998244353
200 100 998244353
32 59 998244853
1 1 998244353

示例输出 3

26831232
94573603
37147649
847564946
727060898
1

---

注释

• 第一个测试用例：只有一种方法生成 $a$，且该序列是确定性最大堆，所以答案是 $1$。
• 第二个测试用例：
  如果选择 $v = 1$ 执行 add，得到 $a = [1,0,0]$，此时 $a_2 = a_3$，第一次 pop 时可任选，所以该堆不是确定性的。
  如果选择 $v = 2$ 执行 add，得到 $a = [1,1,0]$：
  • 第一次 pop 时，$a_2 > a_3$，唯一选择 $x = 2$，$a_1$ 变为 $1$，$v = 2$，然后 $a_2 := -1$，最终 $a = [1,-1,0]$。
    该操作是确定性的，所以这是确定性最大堆。
    同理 $v = 3$ 得到的也是确定性最大堆，所以答案是 $2$。