第一类斯特林数（小 p 大 n）

【题目描述】

带符号的第一类斯特林数 $s(n, k)$ 定义为如下恒等式中的系数：

给定 $n,k$ 与素数 $p$，计算 $s(n, k) \bmod p$。

每组测试包含 $T$ 个询问，且所有询问中的 $p$ 都相同。

【输入】

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

【输出】

每行输出一个 $s(n,k) \bmod p$。

【输入样例】

9 7
0 0
1 0
1 1
5 0
5 1
5 2
5 3
5 4
5 5

【输出样例】

1
0
1
0
3
6
0
4
1

【输入样例2】

7 7
40 0
40 10
40 20
40 30
40 40
1000000007 998244353
1000000000000000000 1000000000000000000

【输出样例2】

0
6
0
6
1
0
1

【数据范围】

• $1 \leq T \leq 200000$
• $2 \leq p \leq 5000$
• $p$ 是素数。
• $0 \leq k \leq n \leq 1000000000000000000$

【来源】

Library Checker（yosupo06） stirling_number_of_the_first_kind_small_p_large_n