Firepersons

Each fireperson is given an integer rank, and these ranks come from an integer sequence defined as follows.

A sequence of order $k$ is defined by its first $k$ terms $a_0, a_1, \dots, a_{k-1}$ and by integer constants $b_1, b_2, \dots, b_k$. For $n \ge k$, the terms follow the recurrence

$$a_n = \left(\sum_{i=1}^{k} a_{n-i}, b_i\right) \bmod 10000.$$

The $i$-th oldest fireperson receives rank $a_i$. Given the parameters of the sequence and an integer $i$, compute the rank of the $i$-th fireperson, that is, the $i$-th term $a_i$ of the sequence.

The input consists of several test cases. Each test case is given on a single line containing the following integers separated by single spaces, in order:

$$k \quad a_0 \ \dots \ a_{k-1} \quad b_1 \ \dots \ b_k \quad i$$

• $1 \le k \le 100$ : the order of the sequence
• $0 \le a_j < 10000$ : the first $k$ terms of the sequence
• $0 \le b_j < 10000$ : the multipliers of the recurrence
• $0 \le i < 1,000,000,000$ : the index of the requested term

The input ends with a line containing a single $0$.

For each test case, print on its own line the $i$-th term $a_i$ of the corresponding sequence. The output lines must appear in the same order as the test cases in the input.