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...
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 ;-)