题目描述

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

核心定义

1. ultra 运算：设集合 $A$ 包含 0 元素，$m = \operatorname{mex}(A)$（$\operatorname{mex}$ 表示集合中未出现的最小非负整数），则 $\operatorname{ultra}(A) = \{ x \oplus (m-1) \mid x \in A \}$（$\oplus$ 为异或运算）。可证明 $\operatorname{ultra}(A)$ 也包含 0。
2. mex-稳定集合：选择包含 0 的集合 $A_0$（元素范围 $0 \sim 2^k - 1$），构造序列 $m_i = \operatorname{mex}(A_i)$、$A_{i+1} = \operatorname{ultra}(A_i)$。若存在下标 $l$，使得对所有 $i \geq l$ 都有 $m_i = m_l$，则 $A_0$ 是 mex-稳定的，$m_l$ 称为 $A_0$ 的 mex-极限。

问题要求

计算满足以下条件的集合 $A_0$ 的个数（答案对质数 $M$ 取模）：

1. $A_0$ 包含 $n$ 个不同元素，范围 $0 \sim 2^k - 1$，且必须包含 0；
2. $A_0$ 是 mex-稳定的；
3. $A_0$ 的 mex-极限等于 $p$。

输入格式

第一行包含一个整数 $M$（$3 \leq M \leq 10^9$），表示模数。保证 $M$ 是质数且 $M-1$ 能被 $2^{18}$ 整除。 第二行包含一个整数 $t$（$1 \leq t \leq 10^5$），表示测试数据的组数。 每组测试数据包含一行三个整数 $k, n, p$（$1 \leq k \leq 17$，$1 \leq n, p \leq 2^k$）。

输出格式

对每组测试数据，输出满足条件的集合 $A_0$ 的个数对 $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$（即 $2^3 - 1$）的整数可构成 7 个 mex-稳定的大小为 2 的集合：$\{0,1\},\{0,2\},\{0,3\},\{0,4\},\{0,5\},\{0,6\},\{0,7\}$。

• 对于 $\{0,1\}$：$\operatorname{mex}(A_0) = 2$，$\operatorname{ultra}(A_0) = \{0 \oplus 1, 1 \oplus 1\} = \{1,0\} = A_0$，故 mex-极限为 2。
• 对于其他 6 个集合：$\operatorname{mex}(A_0) = 1$，$\operatorname{ultra}(A_0) = \{x \oplus 0 \mid x \in A_0\} = A_0$，故 mex-极限为 1。

数据范围与提示

题目包含 30 个子任务，核心限制为 $k \leq 17$、$t \leq 10^5$，所有测试数据的输入规模需适配高效算法。