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

hide comments
coutaditya: 2021-12-23 15:42:33

Accepted in one go :)

terminator0309: 2021-07-19 11:03:18

here MOD is 1e9 not 1e9+7

blueflare99: 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.

jaydip001: 2021-05-16 12:22:28

At last solved the excellent question

terminator2001: 2021-04-10 15:15:28

bc

sanjitpd_777: 2021-04-07 12:50:34

I'm a faggot.

Last edit: 2021-04-07 14:01:23
maheshwari7778: 2021-03-20 09:24:20

Amazing blog
http://zobayer.blogspot.com/2010/11/matrix-exponentiation.html

agga_daku: 2021-01-31 09:59:44

i am getting wrong answer can anybody help?

ashigup11: 2021-01-16 09:06:31

AC in one go

coding_sourabh: 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.


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