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 (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_n-1 × b_d-1 + a_n-2 × b_d-2 + ... + a_n-(d-1) × b₁ + a_n-d × b₀ . With b₀ != 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+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 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⁹+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.