SEQ  Recursive Sequence
Sequence (a_{i}) of natural numbers is defined as follows:
a_{i} = b_{i} (for i <= k)
a_{i} = c_{1}a_{i1} + c_{2}a_{i2} + ... + c_{k}a_{ik} (for i > k)
where b_{j} and c_{j} are given natural numbers for 1<=j<=k. Your task is to compute a_{n} for given n and output it modulo 10^{9}.
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)
b_{1},...,b_{k}  k natural numbers where 0 <= b_{j} <= 10^{9} separated by spaces
c_{1},...,c_{k}  k natural numbers where 0 <= c_{j} <= 10^{9} separated by spaces
n  natural number (1 <= n <= 10^{9})
Output
Exactly C lines, one for each test case: a_{n} modulo 10^{9}
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
Rajat Sharma:
20160806 13:56:12
Java: will learn matrix exponentiation with recursion, linear recursive equations, how to solve these equations by converting the addition into multiplicative expressions i.e. through matrices.


Deepak Singh Tomar:
20160307 15:56:45
matrix_exponentiation. Thanks fushar :) 

minhthai:
20160203 17:26:12
be careful the mod is 10^9 not 10^9 + 7 :) 

Ðức Tân:
20150827 18:45:42
dễ vãi 

r0bo_dart:
20150625 07:28:24
Hint: While doing matrix multiplication, DON'T do temp[][] += mod(F[][] * M[][]);


sHaShAnK sHeKhAr:
20150621 18:23:23
Nice problem to reach 150 :)


i_am_looser:
20150530 15:59:01
learnt something new.......... ; ) 

sai krishna:
20150311 17:52:35
ha ha ha lot of fun in doing it:) 

Ace.JQK:
20141216 11:53:07
multiply matrix 

Francky:
20141202 01:44:19
I guarantee it will be hell to take the #1 ; but possible.

Added by:  Paweł Dobrzycki 
Date:  20050429 
Time limit:  0.5s3s 
Source limit:  8196B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  IV Podlasian Contest in Team Programming 