Cho số nguyên tố \(p\). Với mỗi truy vấn gồm hai số \(n, k\), bạn hãy đếm xem có bao nhiêu cách chọn \(k\) quả táo từ \(n\) quả cho trước. Vì đáp số rất lớn nên bạn chỉ cần in ra đáp số \(\mod p\).

Dữ liệu vào

• Dòng đầu tiên chứa 2 số nguyên dương \(t, p \ (1 \leq t \leq 10^5)\), số lượng truy vấn và số nguyên tố cho trước.
• \(t\) dòng tiếp theo, mỗi dòng chứa 2 số nguyên dương \(n, k\).

Dữ liệu ra

Với mỗi truy vấn, in ra một số nguyên là đáp số của truy vấn đó.

Ví dụ

Input

4 5
4 2
3 2
3 4
7 2

Output

1
3
0
1

Giới hạn

• \(25\%\) số test có \(n, k \leq 1000; p \leq 10^9 + 7\)
• \(25\%\) số test có \(n, k \leq 10^5; p = 10^9 + 7\)
• \(50\%\) số test còn lại có \(n, k \leq 10^5; p \leq 10^9 + 7\)