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

【题目描述】

第二类斯特林数 $S(n, k)$ 定义为下式中的系数：

给定 $n,k$ 和 $p$，其中 $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
1
1
4
3
1

【输入样例2】

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

【输出样例2】

0
6
0
1
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_second_kind_small_p_large_n