这是问题的困难版本。两个版本之间的区别在于确定性最大堆的定义、时间限制以及对 $$$n$$$ 和 $$$t$$$ 的约束。只有当问题的两个版本都得到解决时,你才能进行黑客攻击。
考虑一棵大小为 $$$2^n - 1$$$ 的完美二叉树,节点编号从 $$$1$$$ 到 $$$2^n-1$$$,根为 $$$1$$$。对于每个顶点 $$$v$$$ ($$$1 \le v \le 2^{n - 1} - 1$$$),顶点 $$$2v$$$ 是其左子节点,顶点 $$$2v + 1$$$ 是其右子节点。每个节点 $$$v$$$ 还分配有一个值 $$$a_v$$$。
定义运算 $$$\mathrm{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. 将 $$$-1$$$ 分配给 $$$a_v$$$ (即 $$$a_v := -1$$$)。
如果存在唯一的方法来执行 $$$\mathrm{pop}$$$ 操作,那么我们就说 $$$\mathrm{pop}$$$ 操作是确定性的。换句话说,只要在它们之间进行选择,$$$a_{2v} \neq a_{2v + 1}$$$ 就会成立。
如果对于每个顶点 $$$v$$$ ($$$1 \le v \le 2^{n - 1} - 1$$$),$$$a_v \ge a_{2v}$$$ 和 $$$a_v \ge a_{2v + 1}$$$ 都成立,则二叉树称为最大堆。
如果我们第一次和第二次执行 $$$\mathrm{pop}$$$ 操作对于堆来说是确定性的,则最大堆是确定性的。
最初,$$$a_v := 0$$$ 对于每个顶点 $$$v$$$ ($$$1 \le v \le 2^n - 1$$$),你的目标是计算通过应用以下操作 $$$\mathrm{add}$$$ 精确 $$$k$$$ 次产生的不同确定性最大堆的数量:
- 选择一个整数 $$$v$$$ ($$$1 \le v \le 2^n - 1$$$),并且对于 $$$1$$$ 和 $$$v$$$ 之间路径上的每个顶点 $$$x$$$,将 $$$1$$$ 添加到 $$$a_x$$$。
如果堆中存在一个具有不同值的节点,则认为两个堆不同。
由于答案可能很大,请以 $$$p$$$ 为模打印它。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 50$$$)。测试用例的描述如下。
每个测试用例的第一行包含三个整数 $$$n、k、p$$$($$$2 \le n \le 100$$$、$$$1 \le k \le 500$$$、$$$10^8 \le p \le 10^9$$$、$$$p$$$ 是素数)。
保证所有测试用例的$$$n$$$总和不超过$$$100$$$,并且所有测试用例的$$$k$$$总和不超过$$$500$$$。
输出
对于每个测试用例,输出一行包含一个整数:通过应用上述操作 $$$\mathrm{add}$$$ 恰好 $$$k$$$ 次产生的不同确定性最大堆的数量,以 $$$p$$$ 为模。
示例
输入 #1
6 2 1 998244353 3 2 998244853 3 3 998244353 3 4 100000037 4 2 100000039 4 3 100000037
输出 #1
2 12 40 100 32 224
输入 #2
1 100 500 100000037
输出 #2
66681128
输入 #3
2 87 63 100000037 13 437 100000039
输出 #3
83566569 54517140
注意
对于第一个测试用例,如果我们选择 $$$v = 1$$$ 并执行操作,我们将得到 $$$a = [1, 0, 0]$$$,并且由于 $$$a_2 = a_3$$$,我们可以在执行第一个 $$$\mathrm{pop}$$$ 操作时选择它们中的任何一个,因此这样的堆不是确定性最大堆。
如果我们选择 $$$v = 2$$$,我们就会有 $$$a = [1, 1, 0]$$$,在第一个 $$$\mathrm{pop}$$$ 期间,会发生以下情况:
- 将 $$$v$$$ 初始化为 $$$1$$$
- 由于 $$$a_{2v} > a_{2v + 1}$$$,选择 $$$2v$$$ 作为 $$$x$$$,然后 $$$x = 2$$$
- 将 $$$a_x$$$ 分配给 $$$a_v$$$,然后 $$$a = [1, 1, 0]$$$
- 将 $$$x$$$ 分配给 $$$v$$$,然后 $$$v = 2$$$
- 由于 $$$v$$$ 是叶子,将 $$$-1$$$ 分配给 $$$a_v$$$,然后 $$$a = [1, -1, 0]$$$
在第二个 $$$\mathrm{pop}$$$ 期间,会发生以下情况:
- 将 $$$v$$$ 初始化为 $$$1$$$
- 由于 $$$a_{2v} < a_{2v + 1}$$$,选择 $$$2v + 1$$$ 作为 $$$x$$$,然后 $$$x = 3$$$
- 将 $$$a_x$$$ 分配给 $$$a_v$$$,然后 $$$a = [0, -1, 0]$$$
- 将 $$$x$$$ 分配给 $$$v$$$,然后 $$$v = 3$$$
- 由于 $$$v$$$ 是叶子,将 $$$-1$$$ 分配给 $$$a_v$$$,然后 $$$a = [0, -1, -1]$$$
由于第一个和第二个 $$$\mathrm{pop}$$$ 操作都是确定性的,因此这是一个确定性的最大堆。另外,如果我们选择 $$$v = 3$$$,则 $$$a$$$ 将是确定性最大堆,因此答案是 $$$2$$$。