A linear homogeneous recurrence relation of order d with constant coefficients has the seed values t0, t1, ... td-1 with further terms defined according to tn = c1 tn-1 + c2 tn-2 + ... + cd tn-d. For example, let d = 2. This means that the first two terms t0 and t1 have specified values. Let c1 = c2 = 1, then all terms tn for n > 1 are defined as tn = tn-1 + tn-2. When t0 = 0 and t1 = 1, the sequence begins 0, 1, 1, 2, 3, 5, 8, ... : the Fibonacci sequence.

Given the values of d, t0 ... td-1, and c1 ... cd and a non-negative integer n, can you determine the term tn in this sequence, modulo 10007?

Input
The first line of input contains two integers separated by a space, d (0 < d ≤ 50) and n (0 ≤ n < 109).
Each of the following d lines contains one integer ti (-10000 < ti < 10000). They are given in the order t0, t1, ... td-1.
Each of the following d lines contains one integer ci (-10000 < ci < 10000). They are given in the order c1, c2, ... cd.

Output
Output a single line containing tn modulo 10007.
Note that although the mod operator in your language may give negative results, the answer should be a non-negative integer.
Sample Input
2 10
2 1
1 1

Sample Output
123

Explanation
This sequence is defined according to t0 = 2, t1 = 1, and tn = tn-1 + tn-2 where n > 1. This is the sequence of so-called Lucas numbers, beginning 2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123. (This question was also used in the PEG short questions homework packages.)

Point Value: 15 (partial)
Time Limit: 2.00s
Memory Limit: 16M