F. Noodles and Random Walk
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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$$$.

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.

Example
Input
3
1 1
4 2
6 3
Output
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)$$$