이항 계수

정수 $n,k$와 $m$이 주어질 때, $\binom{n}{k} \bmod m$을 출력한다.

각 테스트는 $T$개의 케이스로 이루어지며, 모든 케이스에서 $m$는 고정되어 있다.

제약 조건

• $1 \leq T \leq 200000$
• $1 \leq m \leq 1000000$
• $0 \leq k \leq n \leq 1000000000000000000$

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

각 줄마다 $\binom{n}{k} \bmod m$을 출력한다.