I. Ajam's Password
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Ajam loves to deal in digital currencies, so he has a digital wallet in which he stores his digital money.

Unfortunately, Ajam forgot his wallet's password, which contained a large amount of money

Ajam only remembers these things about his password:

  • It consists of zeros and ones only.
  • It contains $$$n_0$$$ number of zeros and $$$n_1$$$ number of ones.
  • It shall not contain less than $$$l_0$$$ consecutive zero and no more than $$$r_0$$$ consecutive zero.
  • It shall not contain less than $$$l_1$$$ consecutive one and no more than $$$r_1$$$ consecutive one.

Ajam wants to hire Abdul Rahman to recover his password, can you help Abdul Rahman to find out how many passwords meet the conditions mentioned by Ajam?

Since the number of passwords is very large, print it modulo $$$10^{9} + 7$$$.

Input

The first line contains the number of test cases $$$t$$$ $$$( 1 \le t \le 10^{5} )$$$. A description of the test cases follows.

The first line of each test case contains two integers $$$n_0, n_1$$$ $$$( 100 \le n_0,n_1 \le 10^{5} )$$$ — The number of zeros and the number of ones in the password respectively.

The second line of each test case contains two integers $$$l_0, r_0$$$ $$$( 50 \le l_0 \le r_0 \le n_0 )$$$ — the minimum and maximum number of consecutive zeros in the password respectively.

The third line of each test case contains two integers $$$l_1, r_1$$$ $$$( 50 \le l_1 \le r_1 \le n_1 )$$$ — the minimum and maximum number of consecutive ones in the password respectively.

It is guaranteed that the sum of $$$n_0$$$ and $$$n_1$$$ over all test cases does not exceed $$$2 \cdot 10^{5}$$$

Output

For each test case, output the number of passwords that meet problem conditions modulo $$$10^{9} + 7$$$.

Examples
Input
1
100 100
50 83
50 50
Output
2
Input
1
1000 1000
50 100
50 100
Output
234019247