Firepersons

Time limit1sMemory limit128 MB

Summary

Given the first k terms and multipliers of a linear recurrence modulo 10000, return the i-th term for i up to 10^9.

Level: Medium7 of 10
Topics: Math, Matrix, Divide and conquer, Implementation
Solved: No attempts yet

Problem

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.

Input

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$ .

Output

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.

Examples7

Example 1
Input
```
2 0 1 1 1 6
0
```
Expected output
```
8
```
Example 2
Input
```
2 0 1 1 1 20
0
```
Expected output
```
6765
```
Example 3
Input
```
3 5 7 9 1 1 1 0
3 5 7 9 1 1 1 2
0
```
Expected output
```
5
9
```
Example 4
Input
```
3 1 2 3 1 1 1 3
0
```
Expected output
```
6
```
Example 5
Input
```
2 9999 9999 9999 9999 5
0
```
Expected output
```
2
```
Example 6
Input
```
1 7 3 5
0
```
Expected output
```
1701
```
Example 7
Input
```
3 1 2 3 0 0 1 6
0
```
Expected output
```
1
```