제2종 Stirling 수 (작은 p, 큰 n)

제2종 Stirling 수 $S(n, k)$는 다음 항등식의 계수로 정의된다. $x^n = \sum_{k=0}^n S(n, k) x (x - 1) \cdots (x - (k - 1)).$

$p$가 소수일 때, $n,k$와 $p$가 주어진다. $S(n, k) \bmod p$를 계산한다.

각 테스트는 $T$개의 경우로 구성되며, 모든 경우에서 $p$는 고정되어 있다.

제약 조건

• $1 \leq T \leq 200000$
• $2 \leq p \leq 5000$
• $p$은 소수이다.
• $0 \leq k \leq n \leq 1000000000000000000$

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

각 줄마다 $S(n,k) \bmod p$를 출력한다.