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
In the first sample case, we need to retract the arm from 10 to 3, which is a total of 7 units, but we only have 3 seconds to do so. There is no way for Roger to reach his goal in this case.
In the second sample case, Roger needs to move his arm from 6 to 3. We have 4 seconds to do so. Thus, Roger can choose exactly 1 out of the 4 seconds to rest and still reach the goal.
In the third sample case, Roger has two arms. The first is pointing at coordinate 3, and the second is pointing at coordinate 4. He would like to move them so the first one is at coordinate 1, and the second is at coordinate 2. The 6 ways are
- (3,4) -> (3,4) -> (2,3) -> (1,2)
- (3,4) -> (2,3) -> (2,3) -> (1,2)
- (3,4) -> (2,3) -> (1,2) -> (1,2)
- (3,4) -> (2,4) -> (2,3) -> (1,2)
- (3,4) -> (2,4) -> (1,3) -> (1,2)
- (3,4) -> (2,3) -> (1,3) -> (1,2)
Don't forget to take the answer modulo 1,000,000,007.
