A. Coin Sequences
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Alice flips a fair coin many times and records the results as a binary string, where '0' represents tails and '1' represents heads.

After looking at the string, she counts how many times each adjacent pair appears:

  • '00' appears exactly $$$a$$$ times,
  • '01' appears exactly $$$b$$$ times,
  • '10' appears exactly $$$c$$$ times,
  • '11' appears exactly $$$d$$$ times.

Your task is to determine how many different binary strings satisfy these counts.

Input

The first line contains an integer $$$t$$$ — the number of test cases.

Each test case consists of one line containing four integers $$$a, b, c, d$$$ $$$(1 \le a+b+c+d \le 5 \cdot 10^5)$$$. It is guaranteed that the sum of all $$$a+b+c+d$$$ across all test cases is less than $$$5\cdot 10^5$$$

Output

For each test case, output a single integer — the number of binary strings in which '00' appears $$$a$$$ times, '01' appears $$$b$$$ times, '10' appears $$$c$$$ times, and '11' appears $$$d$$$ times.

Example
Input
5
1 1 1 1
0 2 1 0
3 0 0 3
0 0 3 0
2 3 4 5
Output
4
1
0
0
560
Note
  • The binary string may start with either '0' or '1'.
  • Each adjacent pair contributes exactly once.
  • If no such binary string exists, the answer is $$$0$$$.
  • The answer can be large; output it modulo $$$10^9 + 7$$$.