Bead Games

Ann and Bob found three large jars full of beads. The first jar contained a mixture of red and blue beads. All of the beads in the second jar were yellow and all of the beads in the third jar were green. Ann and Bob decided to play a game with the beads. One of them would think of a number (N) and then each of them would take N beads from the jar containing red and blue beads. Each of them would then arrange their beads in a straight line.

Ann and Bob then decided to create a new line of N beads based on the two lines that they had created. For each of the positions 1 to N in the two lines of beads, they compare the two beads at this position. If the two beads were the same colour they put a yellow bead into the new line. If the two beads were different colours they put a green bead into the new line. Eventually they had a new line of N beads, consisting of yellow and green beads only.

Ann and Bob realised that they could have arranged their lines of red and blue beads in many different ways. This means that there are many possibilities for the new line of yellow and green beads. Ann and Bob wondered whether it was possible to work out just how many different lines of yellow and green beads could be created from the two sets of N red and blue beads. They decided to look at the following simple example where each of them chose just 4 beads. Ann chose 1 red bead and 3 blue beads. Bob chose 2 red beads and 2 blue beads. Ann can arrange her 4 beads in 4 different ways. Bob can arrange his 4 beads in 6 different ways. Hence there are 24 different ways of combining the two sets of beads. These are shown in the table below, together with the corresponding yellow and green line

R B B B   R R B B   Y G Y Y
R B B B   R B R B   Y Y G Y
R B B B   R B B R   Y Y Y G
R B B B   B R R B   G G G Y
R B B B   B R B R   G G Y G
R B B B   B B R R   G Y G G
B R B B   R R B B   G Y Y Y
B R B B   R B R B   G G G Y
B R B B   R B B R   G G Y G
B R B B   B R R B   Y Y G Y
B R B B   B R B R   Y Y Y G
B R B B   B B R R   Y G G G
B B R B   R R B B   G G G Y
B B R B   R B R B   G Y Y Y
B B R B   R B B R   G Y G G
B B R B   B R R B   Y G Y Y
B B R B   B R B R   Y G G G
B B R B   B B R R   Y Y Y G
B B B R   R R B B   G G Y G
B B B R   R B R B   G Y G G
B B B R   R B B R   G Y Y Y
B B B R   B R R B   Y G G G
B B B R   B R B R   Y G Y Y
B B B R   B B R R   Y Y G Y

Although the 24 combinations of red and blue lines are all different, the same is not true of the yellow and green lines. There are only 8 distinct combinations.

You will be given the number of red and blue beads (Ra and Ba) chosen by Ann, as well as the number of red and blue beads (Rb and Bb) chosen by Bob. It is guaranteed that Ra + Ba = Rb + Bb = N. You are to find the total number of distinct lines of yellow and green beads which can be created by following the rules of the game. As this number can be very large you are asked to give the answer modulo 1000000007 (10^9 +7). You can assume that the value of N will always be smaller than one million.

Input and Answer:
The first line of the problem will be a single integer T denoting the number of test cases.
Each test case has a single line of data consisting of 4 integers, Ra, Ba, Rb andBb. For each test case give the number of distinct yellow and green lines that can be made; giving the answer modulo 1000000007. Combine all answers into a single string, separated by single spaces.

Example:

input:
3
1 3 2 2
1 8 6 3
32 3 6 29

answer:
8 162 77663157