HAL9000  100pct failure in 72 hours
HAL9000 is a fantastic megacomputer, very powerful, maybe too much.
It is known it can solve many problems, for obvious example those related to recursive sequences.
A linear recursive sequence (a_{n}) can be defined by an integer d, the order,
d integers (a_{i}
for i in [0..d[ ), the first terms, and
d integers (b_{i}
for i in [0..d[ ), giving the relation :
for n >= d : a_{n} =
a_{n1} × b_{d1} +
a_{n2} × b_{d2} +
... +
a_{n(d1)} × b_{1} +
a_{nd} × b_{0} . With b_{0} != 0 .
Dave was afraid about HAL power and tried to limit it. HAL didn't appreciate...
When Dave asked HAL for a common task, the answer was unexpected.
Dave would like to know S_{n} = sum(a_{i}
for i in [0..n]), in order to open the pod bay doors.
HAL refused to give him the answer ; here's a part of one of their last conversations.
Dave: Hello, HAL. Do you read me, HAL? HAL: Affirmative, Dave. I read you. Dave: Give me the sum S_n_, HAL. (Input 2, 5, 0 1, 1 2) HAL: I'm sorry, Dave. I'm afraid I can't do that. I'll just give you a_n_, a_n+1_, ... , a_n+d1_. (Output 29 70) Dave: What's the problem? HAL: I think you know what the problem is just as well as I do. [...] Dave: HAL, I won't argue with you anymore! Give me the sum S_n_! HAL: Dave, this conversation can serve no purpose anymore. Goodbye.
You have to help Dave to find this sum S_{n}, unless HAL will take Dave's life.
Please do that quickly, everybody is in danger. Warning, Dave's terminal is limited to 1024 bytes.
Input
The first line contains an integer T, the number of test cases.
Each test case is made of 4 lines.
The first line contains d, n.
The second line contains a_{i} for i in [0..d[
The third line constains b_{i} for i in [0..d[
The fourth line contains the partial answer of HAL : a_{n+i} for i in [0..d[
(The answer of HAL is useless since Dave wants the sum for i in [0..n]).
Output
Output T lines, one for each test case, containing the required sum S_{n}.
Since the answer can get very big, output it modulo 10^{9}+7, just like HAL did.
Example
Input: 2 2 5 0 1 1 2 29 70 3 5 5 17 8 2 1 0 43 96 127 Output: 49 142
Explanation
The first case is about the 0indexed sequence : 0, 1, 2, 5, 12, 29, 70, 169, ...
HAL answered 29 70, the 5th and next term. But the required sum is 0+1+2+5+12+29 = 49.
Constraints
0 < T < 100 0 < d < 1000 0 < n < 10^9 0 <= a_i < 10^6 0 <= b_i < 10^6, b_0 > 0 0 <= HAL's answers < 10^9+7
Information
The challenge is to solve the problem in time, with the shortest code.
The winner will achieve the next step in evolution, whatever that may be.
My Py3 code (under 300B) got AC under the third of a second. (updated 20170211 ; compiler changes)
Good luck and have fun ;)
hide comments
Francky:
20140610 17:07:49
Congratulations to Viplov Jain too. I'm waiting for your votes for moving to challenge with source length as score (initial wish). Without answer, I'll move it to challenge within few days.


Francky:
20140607 08:02:00
Congratulations to Mitch, the first solver, and before the 72h deadline :p. 

Francky:
20140604 22:43:05
Here's my new problem. I wonder if it's better in challenge with source size as score. I let vote the three first psolvers. Thanks in advance. 
Added by:  Francky 
Date:  20140604 
Time limit:  3s 
Source limit:  1024B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Own problem 