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
davemaharshi7: 2019-10-04 16:48:37

Anybody here after Coding Blocks tutorial on this ...

neerajamoniya: 2019-09-26 08:20:01

Why is recursion giving TLE ????

divyanshu12312: 2019-08-06 14:05:59

Long Implementation
Matrix Exponentiation

smiling_addu: 2019-07-28 05:59:57

WA in one go.... :)

maratha: 2019-07-26 19:14:21

You might find problem 'Retrospective Sequences' on codeforces gym similar to this.(Slight variation)

Last edit: 2019-07-26 19:15:33
sagar_june97p: 2019-06-12 14:07:21

AC in One go!!!

surajk543: 2018-10-19 14:05:29

Got Accepted Finally...YAAHOOOO>>>

masterchef2209: 2018-09-07 23:30:45

AC in 1 go
good question :D

riyuzaki251097: 2018-08-14 23:10:21

though concept is easier to think but implementation took me hours

hrsh_sengar: 2018-03-14 09:06:48

My 100th :)


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