The government of virtualBit has N ministers. The importance and type of the ith minister is A_{i} and P_{i}. The ministers have decided that the best way to solve the issues quickly is to divide themselves into two groups. The two groups should satisfy the following:
The difference in total importance of ministers of a group must be less than or equal to B.
The ministers work efficiently when they have another minister from the same group and type to brain-storm ideas with. So, ministers of the same type belonging to same group form pairs. The total number of ministers in both groups that do not belong to any pair should be less than or equal to Q.
Your task is to find the total number of ways in which the two groups can be formed.
Input
The first line contains T, the number of test-cases.
T test cases follow.
The first line of each test case contains N, B and Q.
The second line of each test case contains N numbers. The ith number is A_{i}
The third line of each test case contains N numbers. The ith number is P_{i}
Output
For each test case, output a single line containing the number of ways in which the groups can be made.
Since the answer can be very large, output the number of ways modulo 1000000007 (10^{9}+7)
Constraints
1 <= T <= 10
1 <= N <= 100
0 <= A_{i} <= 100
1 <= P_{i} <= 5
0 <= B <= 10^{4}
0 <= Q <= N
In the first case, the only possible way to make two groups are {1,2,5} and {3,4}. This ensures that the difference in sum of two groups is 8 - 7 = 1 and the only unpaired minister is 2
In the second case, there is no way to ensure that the total number of unpaired ministers is <= 4