Given two integers and . In how many ways can items be chosen from items?
Input Format
The first line contains the number of test cases . Each of the next lines contains two integers and .
Constraints
Output Format
Output lines, containing the required answer for the corresponding test case. Output all answers modulo .
Sample Input
4
2 1
4 0
5 2
10 3
Sample Output
2
1
10
120