28462번 - Ультра 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$.