EOJ Test Round #7

D. Binomial

单点时限: 40.0 sec

内存限制: 1024 MB

Given , , , output .

输入格式

In the first line are two integers and (, is prime), meaning the test case number and the prime , respectively.

Next lines each contains 2 integers and ().

输出格式

For each test case, output the binomial modulo .

样例

Input
4 7
4 2
2 1
1 1
5 3
Output
6
2
1
3