SOLVE

LATER

Bonus Money <July Circuits 18>

/

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\).

Explanation

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)\).

Time Limit:
2.0 sec(s)
for each input file.

Memory Limit:
512 MB

Source Limit:
1024 KB

Initializing Code Editor...