q-二项式系数（质模）（q-Binomial Coefficient (Prime Mod)）

问题描述

给定整数 $n, k$、一个整数 $q$ 和一个质数 $m$，计算 q-二项式系数（也称高斯系数）

$$\binom{n}{k}_q \bmod m,$$

其中

$$\binom{n}{k}_q = \frac{(1-q^n)(1-q^{n-1})\cdots(1-q^{n-k+1})}{(1-q^k)(1-q^{k-1})\cdots(1-q)}.$$

注：当 $q \equiv 1 \pmod{m}$ 时，$\binom{n}{k}_q \equiv \binom{n}{k} \pmod{m}$；否则需在模 $m$ 下计算分子分母的乘积并用费马小定理求逆元。

约束条件

• $1 \leq T \leq 10^6$
• $1 \leq m \leq 2^{30}$，且 $m$ 为质数
• $0 \leq q < m$
• $0 \leq k \leq n < \min(m, 10^7)$

输入格式

$T\ m\ q$
$n_0\ k_0$
$n_1\ k_1$
:
$n_{T-1}\ k_{T-1}$

输出格式

对每组输入，输出一行：$\binom{n_i}{k_i}_q \bmod m$

7 998244353 1
6 0
6 1
6 2
6 3
6 4
6 5
6 6

1
6
15
20
15
6
1

7 998244353 2
6 0
6 1
6 2
6 3
6 4
6 5
6 6

1
63
651
1395
651
63
1

7 998244353 0
6 0
6 1
6 2
6 3
6 4
6 5
6 6

1
1
1
1
1
1
1