Cho $t$ truy vấn và giá trị $mod$ $(1\le mod\le 2\ast {10}^9)$, mỗi truy vấn gồm hai số nguyên dương $n$, $k$. Kí hiệu $C(k,n)$ là tổ hợp chập $k$ của $n$, hãy in ra $C(k,n)$ cho mỗi truy vấn tương ứng. Do kết quả có thể rất lớn nên hãy in nó sau khi lấy phần dư cho $mod$.

Subtask

• Sub $1$: $t\le {10}^5$, $1\le k\le n\le 2000$. (30%)
• Sub $2$: $t=1$, $1\le k\le n\le {10}^5$. (30%)
• Sub $3$: $t\le {10}^5$, $1\le k\le n\le {10}^5$, $mod={10}^9+7$. (40%)

Input

• Dòng đầu tiên gồm một số nguyên dương $sub$ miêu tả subtask mà test này tương ứng. ($1\le sub\le 3$)
• Dòng thứ hai gồm hai số nguyên dương $t$ và $mod$.
• $t$ dòng sau, mỗi dòng gồm hai số nguyên dương $n$, $k$ ($k\le n$) miêu tả truy vấn tương ứng.

Output

• In ra $t$ dòng, mỗi dòng là kết quả của truy vấn tương ứng.

Sample Test

Input:

1
3 2345
6 4
8 4
15 8

Output:

15
70
1745