Recursive Sequence#4075

Recursive Sequence

1 saniye

64 megabayt

Çok kolay

A sequence of integers $a_{i}$ a_i is defined as follows:

a_{i} = b_{i} for 1 \leq i \leq k

a_i = b_i \quad \text{for } 1 \leq i \leq k

a_{i} = c_{1} a_{i - 1} + c_{2} a_{i - 2} + \dots + c_{k} a_{i - k}, for i > k

a_i = c_1 a_{i-1} + c_2 a_{i-2} + \cdots + c_k a_{i-k}, \quad \text{for } i > k

where the sequences $b_{j}$ b_j and $c_{j}$ c_j ( $1 \leq j \leq k$ 1 \leq j \leq k) consist of given integer numbers. Your task is to compute $a_{n}$ a_n for a given $n$ and output the result modulo $1 0^{9}$ 10^9.

Giriş

The first line contains the integer $t$ ( $1 \leq t \leq 1 0^{4}$ 1 \leq t \leq 10^4), the number of test cases.

Each test case consists of four lines:

The first line contains a single integer $k$ ( $1 \leq k \leq 10$ 1 \leq k \leq 10) — the length of the sequences $b$ and $c$ .
The second line contains $k$ integers $b_{1}, b_{2}, \dots, b_{k}$ b_1, b_2, \ldots, b_k ( $0 \leq b_{j} \leq 1 0^{9}$ 0 \leq b_j \leq 10^9), the initial values of the sequence.
The third line contains $k$ integers $c_{1}, c_{2}, \dots, c_{k}$ c_1, c_2, \ldots, c_k ( $0 \leq c_{j} \leq 1 0^{9}$ 0 \leq c_j \leq 10^9), the coefficients of the recurrence.
The fourth line contains a single integer $n$ ( $1 \leq n \leq 1 0^{9}$ 1 \leq n \leq 10^9) — the required position in the sequence.

Çıktı

For each test case, print a single integer: the value of $a_{n}$ a_n modulo $1 0^{9}$ 10^9.

Örnekler

Örnek

11
45

Örnek 1