Description

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

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

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

Input Format

第一行包含一个整数 $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$）。

Output Format

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

Hint

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