SEQ - Recursive Sequence

Sequence (ai) of natural numbers is defined as follows:

   ai = bi (for i ≤ k)
   ai = c1ai-1 + c2ai-2 + ... + ckai-k (for i > k)

where bj and cj are given natural numbers for 1 ≤ j ≤ k. Your task is to compute an for given n and output it modulo 109.

Input

On the first row there is the number C of test cases (equal to about 1000).

Each test contains four lines:

k - number of elements of (c) and (b) (1 ≤ k ≤ 10)
b1 ... bk - k natural numbers where 0 ≤ bj ≤ 109 separated by spaces
c1 ... ck - k natural numbers where 0 ≤ cj ≤ 109 separated by spaces
n - natural number (1 ≤ n ≤ 109)

Output

Exactly C lines, one for each test case: an modulo 109.

Example

Input:
3
3
5 8 2
32 54 6
2
3
1 2 3
4 5 6
6
3
24 354 6
56 57 465
98765432

Output:
8
714
257599514

Added by:Paweł Dobrzycki
Date:2005-04-29
Time limit:0.5s-3s
Source limit:8196B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:IV Podlasian Contest in Team Programming

hide comments
2024-06-06 21:26:23
Accepted after tried 13 times. I am not alien that i can solve this in one go.
2024-05-03 08:54:26
mod is okay, but the ordering is confusing. i expected a(n+1) to be b1*c1+b2*c2+...
but turns out b1 is least significant and c1 is most significant
2023-02-11 05:45:59
If you're coding in Java and are struggling with mod, I used long instead of int and then used modulus and it worked for me.

Last edit: 2023-02-11 05:47:44
2021-07-19 11:03:18
here MOD is 1e9 not 1e9+7
2021-06-08 11:07:10
Guys don't fear about fixing %MOD while doing matrix multiplication. It will remain like this only:
res[i][j] = (res[i][j] + (A[i][k]*B[k][j])%MOD)%MOD;

i wasted an hour trying to debug the code by removing MOD and testing again and again lol.

Worry only about getting your matrix Exponentiation function correct.
2021-05-16 12:22:28
At last solved the excellent question
2021-03-20 09:24:20
Amazing blog
http://zobayer.blogspot.com/2010/11/matrix-exponentiation.html
2021-01-31 09:59:44
i am getting wrong answer can anybody help?
2021-01-14 08:47:20
I really wanted to write it atleast once :P , AC in one Go
(Matrix exponentiation) ,
Note : DP can't be used due constraints here.
2020-09-28 13:36:42
@vimi if we use dp then it will give tle use Matrix Exponentiation concept bcz its time complexity is O(k^3 Logn)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.