#GYM104664F. Noodles and Random Walk
Noodles and Random Walk
Description
You are given a noodle with a length of $0$ at time $t = 0$ seconds. Every second, the noodle will either grow or shrink by $1$. The noodle does this for $T$ seconds. A noodle can have negative length.
Calculate the number of ways that the maximum length of the noodle for times $0\leq t\leq T$ is exactly $M$. Output this $\text{mod}\: 10^9 + 7$.
The first line contains $N (1\leq N\leq 10^5)$, the number of test cases.
Then, each of the next $N$ lines will contain two numbers, $T (1\leq T\leq 2000)$, the time that the noodle can either grow or shrink, and $M(1\leq T\leq 2000)$, the maximum length of the noodle.
For each of the $N$ lines, output the number of ways that the maximum length of the noodle for times $0\leq t\leq T$ is exactly $M$ on a new line.
Input
The first line contains $N (1\leq N\leq 10^5)$, the number of test cases.
Then, each of the next $N$ lines will contain two numbers, $T (1\leq T\leq 2000)$, the time that the noodle can either grow or shrink, and $M(1\leq T\leq 2000)$, the maximum length of the noodle.
Output
For each of the $N$ lines, output the number of ways that the maximum length of the noodle for times $0\leq t\leq T$ is exactly $M$ on a new line.
3
1 1
4 2
6 3
1
4
6
Note
For the first case, we can achieve maximum of $1$ using. $(0, 1)$
For the second test case: $(0, 1, 2, 1, 0), (0, 1, 2, 1, 2), (0, -1, 0, 1, 2), (0, 1, 0, 1, 2)$.
For the third test case: $(0, 1, 2, 3, 2, 3, 2), (0, 1, 2, 3, 2, 1, 2), (0, 1, 2, 3, 2, 1, 0), (0, 1, 2, 1, 2, 3, 2), (0, -1, 0, 1, 2, 3, 2), (0, 1, 0, 1, 2, 3, 2)$