The formula for Fibonacci numbers $F_i = 1 dot.op F_{i -1} + 1 dot.op F_{i -2}$ is an example of a linear recurrence relation. Let's consider a more general and difficult formula, which additionally involves the current index $i$.
Consider an infinite sequence defined by its first $n$ elements $a_0, a_1, \\dots, a_{n -1}$ and coefficients $c_1, \\dots, c_n, p, q, r$. For every $i >= n$:
$$a_i = \left(c_1 \cdot a_{i-1} + c_2 \cdot a_{i-2} + \dots + c_n \cdot a_{i-n}\right) + p + i \cdot q + i^2 \cdot r$$
Find the value $a_k bmod 10^9 + 7$.
The first line contains two integers $n$ $(1 <= n <= 10)$ and $k$ $(1 <= k <= 10^(18))$.
The second line contains $n$ integers $a_0, a_1, \\dots, a_(n -1)$ $(0 <= a_i < 10^9 + 7)$ — the first $n$ elements of the sequence.
The third line contains $n$ integers $c_1, c_2, \\dots, c_n$ $(0 <= c_i < 10^9 + 7)$.
The fourth and last line contains three integers $p, q, r$ $(0 <= p, q, r < 10^9 + 7)$.
Print one line containing the number $a_k$ modulo $10^9 + 7$.
In the first sample, the sequence is defined as $a_0 = 0$, $a_1 = 30$, $a_i = (2 a_(i -1) + a_(i -2)) + 2 + i + i^2$, so $a_k = a_2 = (2 dot.op 30 + 0) + 2 + 2 + 4 = 68$.
In the second sample, the first few elements of the sequence are $(5, 14, 38, 85, 163)$. As $k = 3$, we print $a_3 = 85$.
## Input
The first line contains two integers $n$ $(1 <= n <= 10)$ and $k$ $(1 <= k <= 10^(18))$.The second line contains $n$ integers $a_0, a_1, \\dots, a_{n -1}$ $(0 <= a_i < 10^9 + 7)$ — the first $n$ elements of the sequence.The third line contains $n$ integers $c_1, c_2, \\dots, c_n$ $(0 <= c_i < 10^9 + 7)$.The fourth and last line contains three integers $p, q, r$ $(0 <= p, q, r < 10^9 + 7)$.
## Output
Print one line containing the number $a_k$ modulo $10^9 + 7$.
[samples]
## Note
In the first sample, the sequence is defined as $a_0 = 0$, $a_1 = 30$, $a_i = (2 a_(i -1) + a_(i -2)) + 2 + i + i^2$, so $a_k = a_2 = (2 dot.op 30 + 0) + 2 + 2 + 4 = 68$.In the second sample, the first few elements of the sequence are $(5, 14, 38, 85, 163)$. As $k = 3$, we print $a_3 = 85$.
**Definitions**
Let $ n \in \mathbb{Z}^+ $, $ k \in \mathbb{Z}^+ $ with $ 1 \leq n \leq 10 $, $ 1 \leq k \leq 10^{18} $.
Let $ \mathbf{a} = (a_0, a_1, \dots, a_{n-1}) \in \mathbb{Z}^n $ be the initial sequence.
Let $ \mathbf{c} = (c_1, c_2, \dots, c_n) \in \mathbb{Z}^n $ be the recurrence coefficients.
Let $ p, q, r \in \mathbb{Z} $ be constants.
**Recurrence Relation**
For all $ i \geq n $:
$$
a_i = \sum_{j=1}^{n} c_j \cdot a_{i-j} + p + i \cdot q + i^2 \cdot r
$$
**Constraints**
- $ 0 \leq a_i < 10^9 + 7 $ for $ i = 0, 1, \dots, n-1 $
- $ 0 \leq c_j < 10^9 + 7 $ for $ j = 1, \dots, n $
- $ 0 \leq p, q, r < 10^9 + 7 $
**Objective**
Compute $ a_k \mod (10^9 + 7) $.