There are N boxes.
'i'th boxes contains c[i] integers.
'i'th box contains only one type of integer a[i].
Find out in how many number of ways we can select integers from the boxes such that their sum is equal to V.
Number of integers selected from the 'i'th box should me in the range of [0,c[i]].

Input :

First line will contain an integer T (number of test case).
Each test case starts with an integer N.
Next line contains N integers,a[i].
Next line contains N integers,c[i].
Next line contains an integer V.

output :

For every test case, print the required answer modulo 10007.
Print the answer for each test case on a new line.

constraints :
0 ≤ c[i] ≤ 4 : if 'i' is even
0 ≤ c[i] ≤ 3 : if 'i' is odd
a[i] ≤ 10^10
V ≤ 10^10
N ≤ 20

Sample output explanation:

10 =0 * 1 + 2 * 2 + 2 * 3
10 =1 * 1 + 0 * 2 + 3 * 3
10 =2 * 1 + 1 * 2 + 2 * 3
10 =3 * 1 + 2 * 2 + 1 * 3
10 =4 * 1 + 0 * 2 + 2 * 3

total ways = 5%10007 = 5

Problem Setter : Mohd Abdullah
Problem Tester :
Shivam Beri

SAMPLE INPUT
1
3
1 2 3
4 2 4
10

SAMPLE OUTPUT
5

见题面

见题面