E2. Детерминированная куча (сложная версия)
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Разница между двумя версиями заключается в определении детерминированной max-кучи, ограничении на время и ограничениях на $$$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$$$):
    1. среди дочерних вершин $$$v$$$ выбрать ту, значение которой больше, и обозначить такую вершину $$$x$$$; если значения на них равны (то есть $$$a_{2v} = a_{2v + 1}$$$), то можно выбрать любую из них;
    2. присвоить $$$a_x$$$ значению $$$a_v$$$ (т.е. $$$a_v := a_x$$$);
    3. присвоить $$$x$$$ переменной $$$v$$$ (т.е. $$$v := x$$$);
  3. присвоить $$$-1$$$ значению $$$a_v$$$ (т.е. $$$a_v := -1$$$).

Мы говорим, что операция $$$\mathrm{pop}$$$ является детерминированной, если существует единственный способ выполнить такую операцию. Другими словами, $$$a_{2v} \neq a_{2v + 1}$$$ выполняется на каждом шаге операции.

Бинарное дерево называется max-кучей, если для каждой вершины $$$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$$$), и ваша цель — посчитать количество различных детерминированных max-куч, которые можно получить в результате применения следующей операции $$$\mathrm{add}$$$ ровно $$$k$$$ раз:

  • Выбрать целое число $$$v$$$ ($$$1 \le v \le 2^n - 1$$$), и для каждой вершины $$$x$$$ на пути между $$$1$$$ и $$$v$$$ прибавить $$$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$$$.

Выходные данные

Для каждого набора входных данных выведите единственную строку, содержащую целое число: количество различных детерминированных max-куч, которое можно получить в результате применения вышеупомянутой операции $$$\mathrm{add}$$$ ровно $$$k$$$ раз, по модулю $$$p$$$.

Примеры
Входные данные
6
2 1 998244353
3 2 998244853
3 3 998244353
3 4 100000037
4 2 100000039
4 3 100000037
Выходные данные
2
12
40
100
32
224
Входные данные
1
100 500 100000037
Выходные данные
66681128
Входные данные
2
87 63 100000037
13 437 100000039
Выходные данные
83566569
54517140
Примечание

Для первого набора входных данных, если мы выберем $$$v = 1$$$ и выполним операцию, у нас будет $$$a = [1, 0, 0]$$$, а поскольку $$$a_2 = a_3$$$, мы можем выбрать любой из них при выполнении первой операции $$$\mathrm{pop}$$$, поэтому такая куча не является детерминированной max-кучей.

А если мы выберем $$$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}$$$ детерминированы, это детерминированная max-куча. Также, если мы выберем $$$v = 3$$$, то $$$a$$$ будет детерминированной max-кучей, так что ответ — $$$2$$$.