HAL9000 - 100pct failure in 72 hours

no tags 

HAL9000 is a fantastic mega-computer, 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 (an) can be defined by an integer d, the order,
d integers (ai for i in [0..d[ ), the first terms, and
d integers (bi for i in [0..d[ ), giving the relation :
for n >= d : an = an-1 × bd-1 + an-2 × bd-2 + ... + an-(d-1) × b1 + an-d × b0 . With b0 != 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 Sn = sum(ai 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+d-1_. (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 Sn, 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 ai for i in [0..d[
The third line constains bi for i in [0..d[
The fourth line contains the partial answer of HAL : an+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 Sn.
Since the answer can get very big, output it modulo 109+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 0-indexed 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 2017-02-11 ; compiler changes)
Good luck and have fun ;-)

Original Quotes for HAL 9000.


hide comments
Francky: 2014-06-10 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.
--edit--> I got a mail from Mitch with some pros and cons with a great argumentation : many thanks for that ; I really trust in Mitch ; #1 in shorten (Congrats !). There were no conclusions, but arguments, for me, gives a better place in classical, as the golf part seems quite boring when you have 'the(?)' idea.

Last edit: 2014-06-10 19:55:59
Francky: 2014-06-07 08:02:00

Congratulations to Mitch, the first solver, and before the 72h deadline :p.

Francky: 2014-06-04 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:2014-06-04
Time limit:3s
Source limit:1024B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own problem