K. Special Lattice Path
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Little King Terence Tao lives in a 2D grid. He is very fond of food and his favorite restaurant is in $$$(R_x, R_y)$$$ and his Castle is in $$$(0, 0)$$$ coordinate.

But there are some rules: With a single step, if his current position is in $$$(p, q)$$$ coordinate then he can go to any of these five positions $$$(p-1, q+1)$$$, $$$(p, q+1)$$$, $$$(p+1, q+1)$$$, $$$(p+1, q)$$$, $$$(p+1, q-1)$$$ but he has to make sure that he has to stay in the first quadrant, which means he can't cross the axis but can stay on it. Tao can't visit the same co-ordinate twice.

Determine the number of ways he can go to his favorite restaurant.

Input

Input starts with an integer $$$T(1 \le T \le 50000)$$$ — number of test cases.

Each case contains two integers $$$R_x$$$ and $$$R_y$$$ $$$(0 \le R_x, R_y \le 5\cdot 10^7)$$$ — coordinate of the restaurant.

Output

For each case, print the number of ways Tao can visit his favorite restaurant from his castle in a single line. As the result can be huge, you should print the value modulo $$$1000000007$$$ (the remainder when divided by $$$1000000007$$$)

Example
Input
4
2 3
1 5
10 1
0 5
Output
5142
64159
423247468
5142