You are situated in an N dimensional grid at position (x1,x2,...,xN). The dimensions of the grid are (D1,D2,...DN). In one step, you can walk one step ahead or behind in any one of the N dimensions. (So there are always 2×N possible different moves). In how many ways can you take M steps such that you do not leave the grid at any point? You leave the grid if at any point xi, either xi≤0 or xi>Di.

Input Format

The first line contains the number of test cases T. T test cases follow. For each test case, the first line contains N and M, the second line contains x1,x2,…,xN and the 3rd line contains D1,D2,…,DN.

Output Format

Output T lines, one corresponding to each test case. Since the answer can be really huge, output it modulo 1000000007.

Constraints

1≤T≤10

1≤N≤10

1≤M≤300

1≤Di≤100

1≤xi≤Di