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 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.
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$$$)
42 31 510 10 5
5142 64159 423247468 5142
