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\).

Input

• 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\).

Output

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

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(n, k \leq 1000; p \leq 10^9 + 7\)
• Subtask \(2\) (\(25\%\) số điểm): \(n, k \leq 10^5; p = 10^9 + 7\)
• Subtask \(3\) (\(50\%\) số điểm): \(n, k \leq 10^5; p \leq 10^9 + 7\)

Example

 4 5
4 2
3 2
3 4
7 2 

1
3
0
1