Background

Translated from ROI 2023 D1T4.

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$.

Problem Description

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$).

Input Format

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$).

Output Format

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

998244353
6
3 2 1
3 2 2
3 2 3
3 2 4
3 5 1
4 6 1

6
1
0
0
29
2461

Hint

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

Translated by ChatGPT 5