题目描述

译自 ROI 2023 Day1 T4. Ультра mex

定义一个集合 $A$ 上的运算 $\operatorname{ultra}$，$A$ 必须包含 $0$ 元素。设 $m=\operatorname{mex}(A)$，可以发现 $m>0$。我们可以通过如下操作构造一个新的集合 $\operatorname{ultra}(A)$：对 $A$ 中的每个元素，将它异或上 $m-1$。例如，$\operatorname{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$，那么集合 $\operatorname{ultra}(A)$ 也包含 $0$。

我们选择一个由 $0$ 到 $2^{k}-1$ 的整数组成集合 $A_{0}$，它包含 $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})$
• $\ldots$
• $m_{i}=\operatorname{mex}(A_{i}), A_{i+1}=\operatorname{ultra}(A_{i})$
• $\ldots$

如果从某个下标 $l$ 开始，数列 $m_{i}$ 不再变化，我们称集合 $A_{0}$ 是 $\operatorname{mex}$-稳定的。也就是说，对于所有的 $i \geq l$，都有 $m_{i}=m_{l}$。我们把 $m_{l}$ 称为集合 $A_{0}$ 的 $\operatorname{mex}$-极限。

给定三个整数 $k, n, p$，计算满足以下条件的集合 $A_{0}$ 的个数：

• 集合 $A_{0}$ 由 $n$ 个不同的整数组成，范围是从 $0$ 到 $2^{k}-1$（$A_{0}$ 必须包含 $0$ 元素）；
• 集合 $A_{0}$ 是 $\operatorname{mex}$-稳定的；
• 集合 $A_{0}$ 的 $\operatorname{mex}$-极限等于 $p$。

由于答案可能很大，所以请输出答案对一个质数 $M$ 取模的结果。保证 $M-1$ 能被 $2^{18}$ 整除。

输入格式

第一行包含一个整数 $M\ (3 \leq M \leq 10^{9})$，表示答案的模数。保证 $M-1$ 能被 $2^{18}$ 整除且 $M$ 是一个质数。

第二行包含一个整数 $t\ (1 \leq t \leq 10^5)$，表示测试数据的组数。

对于每组测试数据，包含一行三个整数 $k, n, p\ (1 \leq k \leq 17, 1 \leq n, p \leq 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

使用 $0$ 到 $7$ 的整数可以构成 $7$ 个 $\operatorname{mex}$-稳定的大小为 $2$ 的集合：$\{0,1\},\{0,2\},\{0,3\}$, $\{0,4\},\{0,5\},\{0,6\},\{0,7\}$。

对于 $\{0,1\}$，有 $\operatorname{mex}(\{0,1\})=2, \operatorname{ultra}(\{0,1\})=\{0 \oplus 1,1 \oplus 1\}=\{1,0\}=\{0,1\}$，所以 $A_{1}=A_{0}$。因此 $\operatorname{mex}$-极限等于 $2$。

对于其他所有的集合，$m_{0}=\operatorname{mex}(A_{0})=1$，在计算 $\operatorname{ultra}$ 时，所有元素会会异或上 $0$，所以 $\operatorname{ultra}(A_{0})=A_{0}$。因此，对于它们，$\operatorname{mex}$-极限等于 $\operatorname{mex}(A_{0})=1$。

数据范围与提示

这道题目有 $30$ 个子任务。

下表给出了每个子任务对 $k$ 和 $t$ 的限制。对于每个子任务，必须通过所有 $k$ 和 $t$ 的限制不大于它的子任务。