Problem description
Dany jest liniowy ciąg rekurencyjny. Formalnie oznacza to, że podane jest pierwsze k wyrazów ciągu f0, …, fk − 1, a n-ty wyraz ciągu dla n ≥ k określa się wzorem fn = αk ⋅ fn − 1 + … + α1 ⋅ fn − k + α0 dla ustalonego ciągu współczynników α0, …, αk. Twoim zadaniem jest policzyć wartość n-tego elementu tego ciągu modulo 109 + 7.
Wejście
W pierwszym wierszu wejścia znajdują się dwie liczby całkowite k oraz n oznaczające odpowiednio liczbę ustalonych wyrazów ciągu oraz numer poszukiwanego elementu ciągu. W drugim wierszu wejścia następuje k liczb całkowitych f0, …, fk − 1 oznaczających pierwsze k wyrazów ciągu. W trzecim wierszu wejścia znajduje się k + 1 liczb całkowitych $\alpha_0,\ldotss, \alpha_k$ oznaczające współczynniki ciągu.
Wyjście
W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć jedna liczba całkowita określająca wartość fn mod 109 + 7.
Ograniczenia
1 ≤ k ≤ 200, 1 ≤ n ≤ 1018, − 109 ≤ fi, αi ≤ 109.
Przykład
| Wejście | Wyjście | |
|
|