Генератор псевдослучайных чисел

Последовательность псевдослучайных чисел 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-е число этой последовательности.

Input

Во входном файле записаны целые числа в следующем порядке: 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). Числа разделяются пробелами и (или) символами перевода строки.

Output

В выходной файл нужно вывести одно число - X_N.

Examples