Let $A$ be a set of non-negative integers. The minimum non-negative integer that does not occur in $A$ is denoted as $\text{mex}(A)$. For example, $\text{mex}(\{0, 1, 2, 4, 5, 9\}) = 3$. This function is often used, for example, in game theory.

The "bitwise exclusive OR" operation (denoted as "xor" in Pascal, "^" in C++, Python, and Java) for two integers is defined as follows: the $i$-th bit of the result is 1 if and only if one of the numbers has a 1 in this bit and the other has a 0. We will denote this operation with the symbol $\oplus$. For example, $6 \oplus 10 = 110_2 \oplus 1010_2 = 1100_2 = 12$.

Let us define another operation on a set $A$ containing the number 0. The operation will be called "ultra". Let $m = \text{mex}(A)$. Note that $m > 0$. We construct a new set $\text{ultra}(A)$ as follows: apply the "bitwise exclusive OR" with the number $(m-1)$ to all elements of $A$. For example, $\text{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\}$.

It can be shown that if a set $A$ contains 0, then the set $\text{ultra}(A)$ also contains 0.

Choose a set $A_0$ consisting of integers from $0$ to $2^k - 1$ and containing 0. Consider the following sequence: $m_0 = \text{mex}(A_0), A_1 = \text{ultra}(A_0)$ $m_1 = \text{mex}(A_1), A_2 = \text{ultra}(A_1)$ ... $m_i = \text{mex}(A_i), A_{i+1} = \text{ultra}(A_i)$ * ...

We call a set $A_0$ mex-stable if, starting from some index $l$, the numbers $m_i$ stop changing. That is, for all $i \ge l$, $m_i = m_l$. We call the number $m_l$ the mex-limit of the set $A_0$.

You are given numbers $k, n,$ and $p$. Calculate the number of sets $A_0$ that: Consist of $n$ distinct integers from $0$ to $2^k - 1$ (0 must be included in $A_0$); Are mex-stable; * Have a mex-limit of $A_0$ equal to $p$.

Since the answer can be large, output it modulo $M$. It is guaranteed that $(M - 1)$ is divisible by $2^{18}$.

Input

The first line contains a single integer $M$ — the modulus to calculate the answer ($3 \le M \le 10^9$; $(M - 1)$ is divisible by $2^{18}$). It is guaranteed that $M$ is a prime number.

The second line contains a single integer $t$ — the number of test cases ($1 \le t \le 100\,000$).

For each test case, the only line contains three integers $k, n,$ and $p$ ($1 \le k \le 17$; $1 \le n, p \le 2^k$).

Output

For each test case, output a single integer on a new line — the number of such sets $A$, taken modulo $M$.

Examples

Input 1

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

Output 1

6
1
0
0
29
2461

Note

There are a total of 7 mex-stable sets of size 2 from the numbers 0 to 7: $\{0, 1\}, \{0, 2\}, \{0, 3\}, \{0, 4\}, \{0, 5\}, \{0, 6\}, \{0, 7\}$.

For $\{0, 1\}$: $\text{mex}(\{0, 1\}) = 2$, $\text{ultra}(\{0, 1\}) = \{0 \oplus 1, 1 \oplus 1\} = \{1, 0\} = \{0, 1\}$, so $A_1 = A_0$. This means the mex-limit is 2.

For all other sets, $m_0 = \text{mex}(A_0) = 1$, and for them, when calculating $\text{ultra}$, the operation $\oplus$ is performed with the number 0, so $\text{ultra}(A_0) = A_0$. Thus, for them, the mex-limit is equal to $\text{mex}(A_0) = 1$.