K. Center of Attraction?
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Once in CPLand, there was a boy named Monke. In order to impress his friend(also crush) Potato, he decided to be the center of attraction in the assembly line.

The assembly line consists of $$$b$$$ boys and $$$g$$$ girls, standing from left to right. Positions in the assembly line are numbered from $$$1$$$ to $$$b+g$$$, with $$$1$$$ being the leftmost position, $$$b+g$$$ being the rightmost.

Nanavai, the famous teacher of the school makes an arrangement of boys and girls on the assembly line. That is — he selects $$$g$$$ positions, where girls will stand in no particular order. The boys will stand in the remaining positions. Monke thinks he is the center of attraction if at least $$$x$$$ girls standing on his left, and at least $$$y$$$ girls standing on his right.

That is — let $$$i$$$ be the position of Monke on the assembly line, he thinks he is the center of attraction if there are at least $$$x$$$ girls in position from $$$1$$$ to $$$i - 1$$$, and there are at least $$$y$$$ girls in position from $$$i + 1$$$ to $$$b + g$$$. (Yeah, his idea of the center is different from others because he is a genius)

As Monke is the best coder in the town, he can select any position reserved for boys, and stand there. He doesn't yet know the selected arrangement made by Nanavai. He wonders, how many arrangements $$$\bmod 10^9+7$$$ are there for which it's possible for him to be the center of attraction. Can you help him?

Input

The input consists of multiple test cases. The first line contains an integer $$$t\ (1 \le t \le 10^5)$$$ — the number of test cases. The description of the test cases follows.

Each test case contains four integers $$$b, g, x, y \ (1 \le b,g,x,y \le \ 10^6)$$$ — the number of boys, girls, the number of girls Monke wants on his left, the number of girls Monke wants on his right.

Output

For each test case, print the number of arrangements, $$$\bmod$$$ $$$10^9+7$$$ for which it is possible for Monke to be the center of attraction.

Example
Input
2
3 5 2 1
69 420 13 37
Output
46
443945467
Note

One of the possible arrangement for the first test case can be [B, G, G, G, B, G, G, B], where B denotes the position of boys, and G denotes the position of the girls, and Monke's position is underlined. He has $$$3$$$ (at least $$$2$$$) girls on his left and $$$2$$$ (at least $$$1$$$) girls on his right.

Note that Monke can stand in any position that is selected for boys.