제1종 스털링 수(작은 p, 큰 n)

부호 있는 제1종 스털링 수 $s(n, k)$는 다음 항등식의 계수로 정의된다. $x (x - 1) \cdots (x - (n - 1)) = \sum_{k=0}^n s(n, k) x^k.$

$n,k$와 $p$이 주어지며, 여기서 $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$을 출력한다.