We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
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