题目背景

翻译自 ROI 2023 D1T4。

假设 $A$ 是一个非负整数的集合。将 $A$ 中不存在的最小非负整数记为 $\operatorname{mex}(A)$。例如，$\operatorname{mex}(\{0, 1, 2, 4, 5, 9\}) = 3$。

我们还定义了一种在含有 $0$ 的集合 $A$ 上的操作，称为 $\operatorname{Ultra}$。假设 $m = \operatorname{mex}(A)$，因为 $0\in A$，显然 $m > 0$。按照以下方法构建新的集合 $\operatorname{Ultra}(A)$：对 $A$ 中的每个元素异或 $m-1$。例如，$\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\}$。

不难发现，如果集合 $A$ 包含 $0$，则集合 $\operatorname{Ultra}(A)$ 也包含 $0$。

我们选择由 $0$ 到 $2^{k-1}$ 之间的整数组成的集合 $A_0$，且 $0$ 在 $A_0$ 中。考虑以下序列：

• $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)$。

如果从某个数 $l$ 开始，数字 $m_i$ 不再变化，也就是说，对于所有 $i \ge l$，$m_i = m_l$，则称集合 $A_0$ 是 mex-stable 的，将 $m_l$ 称为集合 $A_0$ 的 mex-limit。

题目描述

给定整数 $k,n,p$，计算满足以下条件的集合 $A_0$ 的数量：

• 它包含从 $0$ 到 $2^{k-1}$ 的 $n$ 个不同整数（其中 $0$ 必须包含在 $A_0$ 中）；
• 它是 mex-stable 的；
• 它的 mex-limit 等于 $p$。

由于答案可能很大，输出答案对 $M$ 取模后的结果。保证 $M - 1$ 能被 $2^{18}$（$262144$）整除。

输入格式

第一行包含一个整数 $M$，表示要对其取模的模数（$3 \le M \le 10^9$ 且 $M - 1$ 可被 $2^{18}$ 整除）（所以 $M$ 实际上不可能小于 $2^{18}+1$）。保证 $M$ 是一个质数。

第二行包含一个整数 $t$，表示输入数据的组数（$1 \le t \le 100000$）。

对于每组输入数据，包含三个整数 $k,n,p$（$1 \le k \le 17$，$1 \le n, p \le 2^k$）。

输出格式

对于每组输入数据，输出一行，包含一个整数，表示满足条件的集合 $A$ 的数量对 $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

提示

除样例外，本题有三十个子任务，如下图所示。