All Tracks Problem

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:

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 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⁹+7)

Constraints

1 <= T <= 10

1 <= N <= 100

0 <= A_i <= 100

1 <= P_i <= 5

0 <= B <= 10⁴

0 <= Q <= N