Pseudorandom Number Generator#4810
Accedi

Pseudorandom Number Generator

1 secondo
64 megabyte
Facile

A sequence of pseudorandom numbers X_1, X_2, \ldots, X_i, \ldots is generated as follows: the numbers X_1, X_2, \ldots, X_k are given explicitly, and each subsequent number is computed by the formula:

X_n = (a_1 X_{n-1} + a_2 X_{n-2} + \ldots + a_k X_{n-k} + b) \bmod m

You are required to write a program that computes the -th number of this sequence.

Input

The input file contains integers in the following order: (1 \le k \le 30), (1 \le m \le 1000), a_1, \ldots, a_k (0 \le a_i < m), (0 \le b < m), X_1, \ldots, X_k (0 \le X_i < m), (1 \le N \le 10^{100}). The numbers are separated by spaces and/or newline characters.

Output

Output a single number: X_N.

Esempi

Esempio 1

Loading
Loading