Problem11333--[yosupo] Enumerative Combinatorics - q-Binomial Coefficient (Prime Mod)

11333: [yosupo] Enumerative Combinatorics - q-Binomial Coefficient (Prime Mod)

[Creator : ]
Time Limit : 2.000 sec  Memory Limit : 512 MiB

SubmitSolved: 1Submit Num: 2StatisticsShowOff!

Description

Given integers $n,k,q$ and a prime $m$, print $\binom{n}{k}_q \bmod m$.

Here, $\binom{n}{k}_q$ denotes the $q$-binomial coefficient. 
For the definition of $q$-binomial coefficient, see the Gaussian binomial coefficient.

Each test consists of $T$ cases, and $q$ and $m$ are fixed in all cases.

Input

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

Output

For each line, print $\binom{n}{k}_q \bmod m$.

Constraints

- $1 \leq T \leq 10^6$
- $1 \leq m \leq 2^{30}$
- $m$ is a prime
- $0\leq q \lt m$
- $0 \leq n, k \lt \min(m, 10^7)$

Sample 1 Input 

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

Sample 1 Output 

1
6
15
20
15
6
1

Sample 2 Input 

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

Sample 2 Output 

1
63
651
1395
651
63
1

Sample 3 Input 

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

Sample 3 Output 

1
1
1
1
1
1
1

HINT

Yosupo.

Source/Category

 
Submit