Problem description

Dany jest liniowy ciąg rekurencyjny. Formalnie oznacza to, że podane jest pierwsze k wyrazów ciągu f₀, …, f_k − 1, a n-ty wyraz ciągu dla n ≥ k określa się wzorem f_n = α_k ⋅ f_n − 1 + … + α₁ ⋅ f_n − k + α₀ dla ustalonego ciągu współczynników α₀, …, α_k. Twoim zadaniem jest policzyć wartość n-tego elementu tego ciągu modulo 10⁹ + 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 f₀, …, f_k − 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ść f_n mod  10⁹ + 7.

Ograniczenia

1 ≤ k ≤ 200, 1 ≤ n ≤ 10¹⁸,  − 10⁹ ≤ f_i, α_i ≤ 10⁹.

Przykład

2 5
0 1
1 2 3

193