A linear homogeneous recurrence relation of order ~d~ with constant coefficients has the seed values ~t_0, t_1, \dots, t_{d-1}~ with further terms defined according to ~t_n = c_1 t_{n-1} + c_2 t_{n-2} + \dots + c_d t_{n-d}~. For example, let ~d = 2~. This means that the first two terms ~t_0~ and ~t_1~ have specified values. Let ~c_1 = c_2 = 1~, then all terms ~t_n~ for ~n > 1~ are defined as ~t_n = t_{n-1} + t_{n-2}~. When ~t_0 = 0~ and ~t_1 = 1~, the sequence begins ~0, 1, 1, 2, 3, 5, 8, \dots~ : the Fibonacci sequence.

Given the values of ~d, t_0, \dots, t_{d-1}~, and ~c_1, \dots, c_d~ and a non-negative integer ~n~, can you determine the term ~t_n~ in this sequence, modulo ~10\,007~?

Input Specification

The first line of input contains two integers separated by a space, ~d~ ~(0 < d \le 50)~ and ~n~ ~(0 \le n < 10^9)~.
Each of the following ~d~ lines contains one integer ~t_i~ ~(-10\,000 < t_i < 10\,000)~. They are given in the order ~t_0, t_1, \dots, t_{d-1}~.
Each of the following ~d~ lines contains one integer ~c_i~ ~(-10\,000 < c_i < 10\,000)~. They are given in the order ~c_1, c_2, \dots, c_d~.

Output Specification

Output a single line containing ~t_n \bmod 10\,007~.
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 ~t_0 = 2, t_1 = 1~, and ~t_n = t_{n-1} + t_{n-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.)