406979: GYM102644 G Recurrence With Square

The formula for Fibonacci numbers $$$F_i = 1 \cdot F_{i-1} + 1 \cdot 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, \ldots, a_{n-1}$$$ and coefficients $$$c_1, \ldots, c_n, p, q, r$$$. For every $$$i \geq 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 \leq n \leq 10)$$$ and $$$k$$$ $$$(1 \leq k \leq 10^{18})$$$.

The second line contains $$$n$$$ integers $$$a_0, a_1, \dots, a_{n-1}$$$ $$$(0 \leq 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 \leq c_i < 10^9+7)$$$.

The fourth and last line contains three integers $$$p, q, r$$$ $$$(0 \leq p, q, r < 10^9+7)$$$.

Print one line containing the number $$$a_k$$$ modulo $$$10^9+7$$$.

2 2
0 30
2 1
2 1 1

68

1 3
5
1
2 3 4

85

In the first sample, the sequence is defined as $$$a_0=0$$$, $$$a_1=30$$$, $$$a_i=(2a_{i-1} + a_{i-2}) + 2 + i + i^2$$$, so $$$a_k=a_2=(2 \cdot 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$$$.