Roger is a robot. He has n different arms. Currently, his arms are extended out on a 1 dimensional line. The i-th arm is currently extended a_i units to the right. It is guaranteed that 0 < a₁ < a₂ < ... < a_n.

Roger would like to retract his arms so that his i-th arm is extended b_i units to the right. It is guaranteed that 0 < b₁ < b₂ < ... < b_n and that b_i ≤ a_i.

In one second, Roger can choose any subset of his arms (including the empty set), and retract the chosen subset by one unit to the left. More specifically, this means subtracting one from the coordinates of each of the chosen arms. In addition, he doesn't like his arms getting tangled, so at each intermediate time step, the coordinates of his arms must be in strictly increasing order.

Roger has K seconds to get to the final position. Help him count the number of ways he can do this. Two ways are different if there exists a second in which Roger chose a different set of arms. Since the number of ways can get very large, return the count modulo 1,000,000,007.

Input Format

The first line of the input will contain an integer T, denoting the number of test cases. Each test case will be formatted as follows:
The first line of the test case will contain 2 integers, n, K.
The second line of the test case will contain n integers, a₁,...,a_n
The third line of the test case will contain n integers, b₁,...,b_n

Output Format

Print a single line per test case, the number of ways for Roger to get to the final position, modulo 1,000,000,007.

Constraints

For all files
1 ≤ T ≤ 20
1 ≤ n
1 ≤ K ≤ 1,000,000
1 ≤ b_i ≤ a_i ≤ 1,000,000
The sequences a_i and b_i are in strictly increasing order.

File 1 -- 50 pts:
n = 1

File 2 -- 23 pts:
n = 2

File 3 -- 15 pts:
n ≤ 5

File 4 -- 12 pts:
n ≤ 50