Find the number of strings of length “N” made up of only 3 characters – a, b, c such that “a” occurs at least “min_a” times and at most “max_a” times, “b” occurs at least “min_b” times and at most “max_b” times and “c” occurs at least “min_c” times and at most “max_c” times. Note that all permutations of same string count as 1, so “abc” is same as “bac”.

Input

First line gives T, the number of test cases.

Each test case has an integer “N” on first line.

Next line contains 2 integers, min_a and max_a.

Next line contains 2 integers, min_b and max_b.

Next line contains 2 integers, min_c and max_c.

Output

Output T lines, each containing the required answer modulo 10^9+7.

Constraints

1 <= T <= 1000

1 <= N <= 10^9

1 <= min_a <= max_a <= 10^9

1 <= min_b <= max_b <= 10^9

1 <= min_c <= max_c <= 10^9

Example

Input:
1
3
1 1
1 1
1 1

Output:
1