8863: [yosupo] Enumerative Combinatorics - Stirling Number of the First Kind (Small p, Large n)
[Creator : ]
Description
The signed Stirling numbers of the first kind $s(n, k)$ are defined as the coefficients in the identity
$x (x - 1) \cdots (x - (n - 1)) = \sum_{k=0}^n s(n, k) x^k.$
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 (x - 1) \cdots (x - (n - 1)) = \sum_{k=0}^n s(n, k) x^k.$
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 \leq 200,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
3
6
0
4
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
6
1
0
1