Генератор псевдовипадкових чисел

Послідовність псевдовипадкрвих чисел X_1, X_2, ..., X_i, ... генерується наступним чином: числа X_1, X_2, ...,X_k задаються у явному вигляді, а кожне наступне обчислюється за формулою:

X_n = (a_1X_{n-1} + a_2X_{n-2} + ... + a_kX_{n-k} + b) mod m

Ви повинні написати програму, яка обчислює N-те число цієї послідовності.

Вхідні дані

У вхідному файлі записані цілі числа у наступному порядку: k (1 ≤ k ≤ 30), m (1 ≤ m ≤ 1000), a_1, ..., a_k(0 ≤ a_i < m), b (0 ≤ b < m), X_1, ..., X_k (0 ≤ X_i < m), N (1 ≤ N ≤ 10^100). Числа відокремлюються пропусками та (або) символами переведення рядка.

Вихідні дані

У вихідний файл потрібно вивести одне число - X_N.

Приклади