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
codephilic:
20200928 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) 

horro:
20200727 21:17:08
Standard Matrix Exponentiation problem!!! 

coder_619:
20200720 01:22:09
Ac In 2nd Go.....:) Last edit: 20200720 01:23:31 

rohitkk074:
20200625 09:54:44
@abhi i made the same mistake, was doing % (1e9+7)


abhj:
20200625 00:52:12
1e9 modulo kaun karta hai? Debug karne main adha ghanta chala gaya 

souravbhadra03:
20200615 07:55:06
Accepted


cs215100:
20200520 21:35:01
tle in java. same code ac in c++. 

jaybatra:
20200502 18:48:59
can someone explain when I used python 3 it gives TLE but when i used C++ using same logic of matrix exponentiation it passed all the test cases why? 

jaybatra:
20200501 10:46:53
I have tried the question using python 3 it is passing the given examples but at the time of submitting it is giving TLE can someone help? 

vimi:
20200425 20:36:32
can we apply DP with some memoization? because surely we have overlapping subproblems 
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 