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