Bonus Money
Tag(s):

## Counting, Dynamic programming, Hard, Math, Special Numbers

Problem
Editorial
Analytics

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$.
SAMPLE INPUT
2 1000000007
2 5
3 3


SAMPLE OUTPUT
3
3

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
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

July Circuits '18

OTHER PROBLEMS OF THIS CHALLENGE
• Math > Basic Geometry
• Algorithms > Graphs
• Math > Number Theory
• Algorithms > Searching
• Algorithms > Searching