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\le T \le 10^5, 1 \le N \le 10^3, 1 \le M \le 10^3, 1 \le P \le 10^9 + 7\).
Subtask 2: \(T = 1, 1 \le N \le 2\times 10^5, 1 \le M \le 2\times 10^5, 1 \le P \le 10^9 + 7\).
Subtask 3: \(1\le T \le 10^5, 1\le N \le 10, 1\le M < 10^{10^5}, P = 10^9 + 7\). The total length of \(M\) over all test cases doesn't exceed \(2\times10^6\).