Retract
Practice
4.1 (28 votes)
Ready
Linear algebra
Hard
Approved
Mathematics
Problem
40% Success 214 Attempts 50 Points 5s Time Limit 256MB Memory 1024 KB Max Code

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 biai.

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 ≤ biai ≤ 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

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:50
4 votes
Tags:
Linear AlgebraHardOpenApprovedMathematics
Points:50
8 votes
Tags:
Linear AlgebraHardOpenApprovedMathematics