E1. Детерминированная куча (простая версия)
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
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 500$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит три целых числа $$$n, k, p$$$ ($$$1 \le n, k \le 500$$$, $$$10^8 \le p \le 10^9$$$, $$$p$$$ — простое).

Гарантируется, что сумма $$$n$$$ и сумма $$$k$$$ по всем наборам входных данных не превосходят $$$500$$$.

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

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

Примеры
Входные данные
7
1 13 998244353
2 1 998244353
3 2 998244853
3 3 998244353
3 4 100000037
4 2 100000039
4 3 100000037
Выходные данные
1
2
12
52
124
32
304
Входные данные
1
500 500 100000007
Выходные данные
76297230
Входные данные
6
87 63 100000037
77 77 100000039
100 200 998244353
200 100 998244353
32 59 998244853
1 1 998244353
Выходные данные
26831232
94573603
37147649
847564946
727060898
1
Примечание

Для первого набора входных данных существует только один способ сгенерировать $$$a$$$, и такая последовательность является детерминированной max-кучей, поэтому ответ — $$$1$$$.

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