8864: [yosupo] Enumerative Combinatorics - Stirling Number of the Second Kind (Small p, Large n)
[Creator : ]
Description
The Stirling numbers of the second kind $S(n, k)$ are defined as the coefficients in the identity
$x^n = \sum_{k=0}^n S(n, k) x (x - 1) \cdots (x - (k - 1)).$
Given $n,k$ and $p$, where $p$ is a prime. Calculate $S(n, k) \bmod p$.
Each test consists of $T$ cases, and $p$ is fixed in all cases.
$x^n = \sum_{k=0}^n S(n, k) x (x - 1) \cdots (x - (k - 1)).$
Given $n,k$ and $p$, where $p$ is a prime. Calculate $S(n, k) \bmod p$.
Each test consists of $T$ cases, and $p$ is fixed in all cases.
Input
$T\ p$
$n_0\ k_0$
$n_1\ k_1$
$\vdots$
$n_{T-1}\ k_{T-1}$
$n_0\ k_0$
$n_1\ k_1$
$\vdots$
$n_{T-1}\ k_{T-1}$
Output
For each line, print $S(n,k) \bmod p$.
Constraints
- $1 \leq T \leq200,000$
- $2 \leq p \leq 5,000$
- $p$ is a prime.
- $0 \leq k \leq n \leq 10^{18}$
- $2 \leq p \leq 5,000$
- $p$ is a prime.
- $0 \leq k \leq n \leq 10^{18}$
Sample 1 Input
9 7
0 0
1 0
1 1
5 0
5 1
5 2
5 3
5 4
5 5
Sample 1 Output
1
0
1
0
1
1
4
3
1
Sample 2 Input
7 7
40 0
40 10
40 20
40 30
40 40
1000000007 998244353
1000000000000000000 1000000000000000000
Sample 2 Output
0
6
0
1
1
0
1