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 ai units to the right. It is guaranteed that 0 < a1 < a2 < ... < an.
Roger would like to retract his arms so that his i-th arm is extended bi units to the right. It is guaranteed that 0 < b1 < b2 < ... < bn and that bi ≤ ai.
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, a1,...,an
The third line of the test case will contain n integers, b1,...,bn
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 ≤ bi ≤ ai ≤ 1,000,000
The sequences ai and bi 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