Задачи
Генератор псевдослучайных чисел
Генератор псевдослучайных чисел
Последовательность псевдослучайных чисел \textbf{X_1}, \textbf{X_2}, ..., \textbf{X_i}, ... генерируется следующим образом: числа \textbf{X_1}, \textbf{X_2}, ...,\textbf{X_k} задаются в явном виде, а каждое следующее вычисляется по формуле:
\textbf{X_n = (a_1X_\{n-1\} + a_2X_\{n-2\} + ... + a_kX_\{n-k\} + b) mod m}
Вы должны написать программу, вычисляющую \textbf{N}-е число этой последовательности.
\InputFile
Во входном файле записаны целые числа в следующем порядке: \textbf{k} (\textbf{1} ≤ \textbf{k} ≤ \textbf{30}), \textbf{m} (\textbf{1} ≤ \textbf{m} ≤ \textbf{1000}), \textbf{a_1}, ..., \textbf{a_k}(\textbf{0} ≤ \textbf{a_i} < \textbf{m}), \textbf{b} (\textbf{0} ≤ \textbf{b} < \textbf{m}), \textbf{X_1}, ..., \textbf{X_k} (\textbf{0} ≤ \textbf{X_i} < \textbf{m}), \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{10^100}). Числа разделяются пробелами и (или) символами перевода строки.
\OutputFile
В выходной файл нужно вывести одно число - \textbf{X_N}.
Входные данные #1
2 5 1 2 3 4 0 3
Выходные данные #1
1