SPP  Recursive Sequence (Version II)
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_{m} + a_{m+1} + a_{m+2} + ... + a_{n} for given m <= n and output it modulo a given positive integer p.
Input
On the first row there is the number C of test cases (equal to about 50).
Each test contains four lines:
k  number of elements of (c) and (b) (1 <= k <= 15)
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.
m, n, p  natural numbers separated by spaces (1 <= m <= n <= 10^{18}, 1<= p <= 10^{8}).
Output
Exactly C lines, one for each test case: (a_{m} + a_{m+1} + a_{m+2} + ... + a_{n}) modulo p.
Example
Input: 1 2 1 1 1 1 2 10 1000003 Output: 142
hide comments
v1a9r9u8n:
20181015 10:58:20
Can't we use the idea of sum of geometric progression somehow? Last edit: 20181015 11:31:31 

ayush926:
20180627 16:33:07
Matrix exponentiation. Learned a lot! 

hazard_10:
20180513 04:08:00
I am getting TLE on using Matrix exponentiation any hints ?? 

galang:
20160915 17:30:09
%I64d gives wa


Yash:
20150217 12:24:35
Nice Question...Good exercise for Matrix Expo :) 

ISHANI:
20150203 20:22:41
Simple as SEQ... 

Curiosa:
20130701 06:42:46
This one sample test is as useless as 'g' in lasagna. @Author Please provide some other tests. 

Sandeep Singh Jakhar:
20130101 06:38:45
Finally...got it Last edit: 20130101 06:39:16 

(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20121230 10:32:11
It's very hard to get accepted with python code, My top speed C code "for now" AC in 0.05s, same algo with python 2 and python 3 but TLE (>7s)... 

[Rampage] Blue.Mary:
20121121 04:51:42
After solving this, try http://www.spoj.pl/problems/SPP2/ 
Added by:  Fudan University Problem Setters 
Date:  20080515 
Time limit:  3s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: C99 ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  Problem SEQ 