{"raw_statement":[{"iden":"statement","content":"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$.\n\nConsider 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$:\n\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$$\n\nFind the value $a_k bmod 10^9 + 7$.\n\nThe first line contains two integers $n$ $(1 <= n <= 10)$ and $k$ $(1 <= k <= 10^(18))$.\n\nThe 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.\n\nThe third line contains $n$ integers $c_1, c_2, \\\\dots, c_n$ $(0 <= c_i < 10^9 + 7)$.\n\nThe fourth and last line contains three integers $p, q, r$ $(0 <= p, q, r < 10^9 + 7)$.\n\nPrint one line containing the number $a_k$ modulo $10^9 + 7$.\n\nIn 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$.\n\nIn the second sample, the first few elements of the sequence are $(5, 14, 38, 85, 163)$. As $k = 3$, we print $a_3 = 85$.\n\n"},{"iden":"input","content":"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)$."},{"iden":"output","content":"Print one line containing the number $a_k$ modulo $10^9 + 7$."},{"iden":"examples","content":"Input2 2\n0 30\n2 1\n2 1 1\nOutput68\nInput1 3\n5\n1\n2 3 4\nOutput85\n"},{"iden":"note","content":"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$."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $, $ k \\in \\mathbb{Z}^+ $ with $ 1 \\leq n \\leq 10 $, $ 1 \\leq k \\leq 10^{18} $.  \nLet $ \\mathbf{a} = (a_0, a_1, \\dots, a_{n-1}) \\in \\mathbb{Z}^n $ be the initial sequence.  \nLet $ \\mathbf{c} = (c_1, c_2, \\dots, c_n) \\in \\mathbb{Z}^n $ be the recurrence coefficients.  \nLet $ p, q, r \\in \\mathbb{Z} $ be constants.  \n\n**Recurrence Relation**  \nFor all $ i \\geq n $:  \n$$\na_i = \\sum_{j=1}^{n} c_j \\cdot a_{i-j} + p + i \\cdot q + i^2 \\cdot r\n$$\n\n**Constraints**  \n- $ 0 \\leq a_i < 10^9 + 7 $ for $ i = 0, 1, \\dots, n-1 $  \n- $ 0 \\leq c_j < 10^9 + 7 $ for $ j = 1, \\dots, n $  \n- $ 0 \\leq p, q, r < 10^9 + 7 $  \n\n**Objective**  \nCompute $ a_k \\mod (10^9 + 7) $.","simple_statement":"Given a sequence defined by first n terms and a recurrence:  \na_i = (c1*a_{i-1} + c2*a_{i-2} + ... + cn*a_{i-n}) + p + i*q + i^2*r,  \nfind a_k mod (10^9 + 7).","has_page_source":false}