In a company, there are N employees. Their productivities are numbered from 1 to N, each employee is assigned with an unique number. At the end of year, their boss decided to reward M bonus money for them. The rule is that if A's productivity is greater than B's one then A's money must not less than B's money. Your task is to find the number of ways to divide M bonus money among N employees acoording to above rule. As the answer can be very large, you only need to find it modulo P.
Input Format
The first line contains two space-separated integers T,P denoting the number of test cases and the modulo.
Each test case is described in a single line containing two space-separated integers N,M.
Output Format
For each test case, output a single line containing the answer.
Constraints
- Subtask 1: 1≤T≤105,1≤N≤103,1≤M≤103,1≤P≤109+7.
- Subtask 2: T=1,1≤N≤2×105,1≤M≤2×105,1≤P≤109+7.
- Subtask 3: 1≤T≤105,1≤N≤10,1≤M<10105,P=109+7. The total length of M over all test cases doesn't exceed 2×106.
Query 1: there are three ways, that are: (0,5),(1,4),(2,3).
Query 2: there are three ways, that are: (0,0,3),(0,1,2),(1,1,1).
