Ультра mex

Рассмотрим $A$ --- множество неотрицательных целых чисел. Минимальное неотрицательное целое число, которое не встречается в $A$, обозначим как $\mathrm{mex}(A)$. Например, $\mathrm{mex}(\\{0, 1, 2, 4, 5, 9\\}) = 3$. Эта функция часто используется, например, в теории игр.

Операция <<побитовое исключающее или>> (обозначается <<xor>> в Паскале и Python, <<\char 94>> в C++ и Java) для двух целых чисел определена следующим образом: $i$-й бит результата равен $1$ тогда и только тогда, когда в одном из чисел этот бит $1$, а в другом $0$. Будем обозначать эту операцию символом $\oplus$. Например, $6 \oplus 10 = 110\_2 \oplus 1010\_2 = 1100\_2 = 12$.

Определим ещё одну операцию над множеством $A$, содержащим число $0$. Операция будет называться <<ультра>>. Пусть $m = \mathrm{mex}(A)$. Заметим, что $m > 0$. Построим новое множество $\mathrm{ultra}(A)$ следующим образом: применим <<побитовое исключающее или>> с числом $(m - 1)$ ко всем элементам $A$. Например, $\mathrm{ultra}(\\{0, 1, 2, 4, 5, 9\\}) = \\{0 \oplus 2, 1 \oplus 2, 2\oplus 2, 4\oplus 2, 5\oplus 2, 9\oplus 2\\}=\\{2, 3, 0, 6, 7, 11\\} = \\{0, 2, 3, 6, 7, 11\\}$. Можно показать, что если множество $A$ содержит $0$, то множество $\mathrm{ultra}(A)$ также содержит $0$.

Выберем множество $A\_0$, состоящее из целых чисел от $0$ до $2^k-1$ и содержащее $0$. Рассмотрим следующую последовательность:

• $m\_0 = \mathrm{mex}(A\_0)$, $A\_1 = \mathrm{ultra}(A\_0)$
• $m\_1 = \mathrm{mex}(A\_1)$, $A\_2 = \mathrm{ultra}(A\_1)$
• $\dots$
• $m\_i = \mathrm{mex}(A\_i)$, $A\_{i + 1} = \mathrm{ultra}(A\_i)$
• $\dots$

Будем называть множество $A\_0$ $\mathrm{mex}$-стабильным, если начиная с некоторого индекса $l$ числа $m\_i$ перестают меняться. То есть, для всех $i \ge l$ выполнено $m\_i = m\_l$. Число $m\_l$ будем называть $\mathrm{mex}$-пределом множества $A\_0$.

Вам даны числа $k$, $n$ и $p$. Вычислите количество множеств $A\_0$, которые:

• Состоят из $n$ различных чисел от $0$ до $2^k - 1$ ($0$ обязательно должен входить в $A\_0$);
• Являются $\mathrm{mex}$-стабильными;
• $\mathrm{mex}$-предел $A\_0$ равен $p$.

Так как ответ может быть большим, выведите его по простому модулю $M$. Гарантируется, что $(M-1)$ делится на $2^{18}$.

В первой строке дано одно целое число $M$ --- модуль, по которому нужно посчитать ответ ($3 \leq M \leq 10^9$; $(M-1)$ делится на $2^{18}$). Гарантируется, что $M$ простое число.

Во второй строке дано одно целое число $t$ --- количество наборов входных данных ($1 \le t \le 100\\,000$).

Для каждого набора входных данных в единственной строке даны три целых числа $k$, $n$ и $p$ ($1 \le k \le 17$; $1 \le n, p \le 2^k$).

Для каждого набора входных данных на новой строке выведите одно целое число --- количество искомых множеств $A$, взятое по модулю $M$.

Всего существует $7$ $\mathrm{mex}$-стабильных множеств размера $2$ из чисел от $0$ до $7$: $\\{0, 1\\}$, $\\{0, 2\\}$, $\\{0, 3\\}$, $\\{0, 4\\}$, $\\{0, 5\\}$, $\\{0, 6\\}$, $\\{0, 7\\}$.

Для $\\{0, 1\\}$: $\mathrm{mex}(\\{0, 1\\})$ = 2, $\mathrm{ultra}(\\{0, 1\\})=\\{0 \oplus 1, 1 \oplus 1\\} = \\{1, 0\\} = \\{0, 1\\}$, получается, что $A\_1 = A\_0$. Значит $\mathrm{mex}$-предел будет равен $2$.

Для всех остальных множеств $m\_0 = \mathrm{mex}(A\_0)=1$, для них при вычислении ultra происходит $\oplus$ с числом 0, поэтому $\mathrm{ultra}(A\_0) = A\_0$. Получается, для них $\mathrm{mex}$-предел равен $\mathrm{mex}(A\_0) = 1$.