All Tracks>Problem
Turbulent Teamwork
★★★★★

0

0 votes
Medium
Problem

The government of virtualBit has N ministers. The importance and type of the ith minister is Ai and Pi. 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:

  1. The difference in total importance of ministers of a group must be less than or equal to B.

  2. 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 Ai

The third line of each test case contains N numbers. The ith number is Pi

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 (109+7)

Constraints

1 <= T <= 10

1 <= N <= 100

0 <= Ai <= 100

1 <= Pi <= 5

0 <= B <= 104

0 <= Q <= N

Sample Input
2
5 1 1
1 2 3 4 5
2 1 1 1 2
5 10 4
1 1 1 1 1
1 2 3 4 5
Sample Output
1
0
Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

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

Editor Image

?