Počet spôsobov ako môžeme z $n$ vecí vybrať práve $k$, nezávisle na poradí, sa rovná $n \cdot (n-1) \cdot ... \cdot (n-k+1) / k!$; toto číslo zapisujeme $n \choose k$; číslo $n \choose k$ je vlastne číslo v $n$-tom riadku a $k-1$-om stĺpci Pascalovho trojuholníku.
Pre dané $n,k$ nájdite $n \choose k$. Keďže tieto čísla môžu byť veľmi veľké, vypíšte ho modulo prvočíslo $p$.
V prvom riadku je číslo $1 \leq t \leq 10^4$ - počet testov a prvočíslo $2 \leq p \leq 2*10^9$. Nasleduje $t$ riadkov, v každom z nich sú dve čísla $0 \leq n,k \leq 10^6$.
Pre každý test vypíšte zvyšok čísla $n \choose k$ po delení číslom $p$.
6 1000000007
10 10
10 0
0 10
100 2
100 7
654321 123456
1
1
0
4950
7560688
475312721