eolymp
bolt
Try our new interface for solving problems
Problems

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

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

Time limit 1 second
Memory limit 64 MiB

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

Во входном файле записаны целые числа в следующем порядке: k (1k30), m (1m1000), a_1, ..., a_k(0a_i < m), b (0b < m), X_1, ..., X_k (0X_i < m), N (1N10^100). Числа разделяются пробелами и (или) символами перевода строки.

Output data

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

Examples

Input example #1
2 5
1 2 3
4 0
3
Output example #1
1