Это простая версия задачи. Разница между двумя версиями заключается в определении детерминированной 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$.