设 $A$ 为一个非负整数集合。我们将 $A$ 中未出现的最小非负整数记为 $\text{mex}(A)$。例如，$\text{mex}(\{0, 1, 2, 4, 5, 9\}) = 3$。该函数在博弈论等领域中经常被使用。

“按位异或”运算（在 Pascal 中记为 xor，在 C++、Python 和 Java 中记为 ^）对于两个整数定义如下：结果的第 $i$ 位为 1 当且仅当两个数中该位一个为 1 而另一个为 0。我们将此运算记为 $\oplus$。例如，$6 \oplus 10 = 110_2 \oplus 1010_2 = 1100_2 = 12$。

我们对包含数字 0 的集合 $A$ 定义另一种运算，称为“ultra”。设 $m = \text{mex}(A)$。注意 $m > 0$。我们按如下方式构造新集合 $\text{ultra}(A)$：将集合 $A$ 中的所有元素与 $(m-1)$ 进行“按位异或”运算。例如，$\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\}$。 可以证明，如果集合 $A$ 包含 0，则集合 $\text{ultra}(A)$ 也包含 0。

选择一个由 $0$ 到 $2^k - 1$ 之间的整数组成且包含 0 的集合 $A_0$。考虑以下序列： $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)$ * ...

如果从某个索引 $l$ 开始，数字 $m_i$ 不再变化，我们称集合 $A_0$ 为 mex-稳定的。即对于所有 $i \ge l$，满足 $m_i = m_l$。我们将数字 $m_l$ 称为集合 $A_0$ 的 mex-极限。

给定数字 $k, n$ 和 $p$。请计算满足以下条件的集合 $A_0$ 的数量： 由 $0$ 到 $2^k - 1$ 之间的 $n$ 个不同整数组成（0 必须包含在 $A_0$ 中）； 是 mex-稳定的； * $A_0$ 的 mex-极限等于 $p$。

由于答案可能很大，请输出其对素数 $M$ 取模的结果。保证 $(M - 1)$ 能被 $2^{18}$ 整除。

输入格式

第一行包含一个整数 $M$ — 计算答案所用的模数（$3 \le M \le 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$ 取模。

样例

样例输入 1

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

样例输出 1

6
1
0
0
29
2461

说明

总共存在 7 个大小为 2 且由 0 到 7 之间的数字组成的 mex-稳定集合：$\{0, 1\}, \{0, 2\}, \{0, 3\}, \{0, 4\}, \{0, 5\}, \{0, 6\}, \{0, 7\}$。

对于 $\{0, 1\}$：$\text{mex}(\{0, 1\}) = 2, \text{ultra}(\{0, 1\}) = \{0 \oplus 1, 1 \oplus 1\} = \{1, 0\} = \{0, 1\}$，得到 $A_1 = A_0$。因此 mex-极限等于 2。

对于所有其他集合，$m_0 = \text{mex}(A_0) = 1$，对于它们，在计算 ultra 时发生与数字 0 的 $\oplus$ 运算，因此 $\text{ultra}(A_0) = A_0$。结果对于它们来说，mex-极限等于 $\text{mex}(A_0) = 1$。