Divisibility

You are in the system of N -dimensional infinite hyper-grid with each hyper cell having an integer. In an N -dimensional grid the co-ordinates of a cell are denoted as (X1, X2, . . . , XN ). Any hyper cell with at least one negative co-ordinate contains the value 0 (zero). The origin hyper cell (the one with all zero co-ordinates) contains the value 1. The value of a hyper cell with co-ordinate (X1, X2, . . . , XN ) (with all non-negative Xi) is the sum of the values in N hyper cells with co-ordinates (X1 − 1, X2, . . . , XN ), (X1, X2 − 1, . . . , XN ), . . . , (X1, X2, . . . , XN − 1). You are given the starting and ending co-ordinate of a subhypercube. You need to compute how many hyper cells in this sub hypercube contain an integer not divisible by a given prime P .

Input

First line of the input contains T (0 < T < 51) the number of test cases. Each test case starts with a line containing N (0 < N < 8) the dimension of the hypercube and the prime P (1 < P < 20). The second line contains N integers denoting the co-ordinate of the starting cell of the hypercube. The third line contains N integers denoting the co-ordinate of the ending cell of the hypercube. All the co-ordinates will be non negative integers with at most 15 digits.

Output

For each test case, print the serial of output followed by the number of hyper cells in the given sub hypercube that contains an integer not divisible by a given prime P . Since the result can be too big so output the result modulo 1000000009. Look at the output for sample input for details.

#12581Divisibility

Input

Output