P11107 [ROI 2023] Ultra mex (Day 1)

Translated from [ROI 2023 D1T4](https://neerc.ifmo.ru/school/archive/2022-2023/ru-olymp-roi-2023-day1.pdf). Suppose $A$ is a set of non-negative integers. Let the smallest non-negative integer that does not belong to $A$ be denoted by $\operatorname{mex}(A)$. For example, $\operatorname{mex}(\{0, 1, 2, 4, 5, 9\}) = 3$. We also define an operation on a set $A$ that contains $0$, called $\operatorname{Ultra}$. Let $m = \operatorname{mex}(A)$. Since $0 \in A$, clearly $m > 0$. We construct a new set $\operatorname{Ultra}(A)$ as follows: XOR every element of $A$ with $m - 1$. For example, $\operatorname{Ultra}(\{0, 1, 2, 4, 5, 9\}) = \{0\oplus2, 1\oplus2, 2\oplus2, 4\oplus2, 5\oplus2, 9\oplus2\} = \{2, 3, 0, 6, 7, 11\} = \{0, 2, 3, 6, 7, 11\}$. It is not hard to see that if the set $A$ contains $0$, then the set $\operatorname{Ultra}(A)$ also contains $0$. We choose a set $A_0$ consisting of $n$ distinct integers between $0$ and $2^{k} - 1$, and $0$ is in $A_0$. Consider the following sequence: - $m_0 = \operatorname{mex}(A_0), A_1 = \operatorname{Ultra}(A_0)$. - $m_1 = \operatorname{mex}(A_1), A_2 = \operatorname{Ultra}(A_1)$. - $\dots$ - $m_i = \operatorname{mex}(A_i), A_{i+1} = \operatorname{Ultra}(A_i)$. If starting from some number $l$, the values $m_i$ no longer change, that is, for all $i \ge l$, $m_i = m_l$, then the set $A_0$ is called mex-stable, and $m_l$ is called the mex-limit of the set $A_0$.

Given integers $k, n, p$, compute the number of sets $A_0$ that satisfy the following conditions: - It contains $n$ distinct integers from $0$ to $2^{k} - 1$ (and $0$ must be included in $A_0$). - It is mex-stable. - Its mex-limit equals $p$. Since the answer may be large, output the result modulo $M$. It is guaranteed that $M - 1$ is divisible by $2^{18}$ ($262144$).

The first line contains an integer $M$, the modulus to take (where $3 \le M \le 10^9$ and $M - 1$ is divisible by $2^{18}$, so in fact $M$ cannot be less than $2^{18} + 1$). It is guaranteed that $M$ is a prime. The second line contains an integer $t$, the number of test cases ($1 \le t \le 100000$). For each test case, there are three integers $k, n, p$ ($1 \le k \le 17$, $1 \le n, p \le 2^k$).

For each test case, output one line containing one integer, the number of sets $A$ that satisfy the conditions modulo $M$.

In addition to the samples, this problem has thirty subtasks, as shown in the figure below.  Translated by ChatGPT 5