Read problems statements in Mandarin chinese, Russian and Vietnamese as well.

You are given two sequences $A$ and $B$, each with size $M$, and an integer $N$. Consider the following pseudocode:

result := 0
for i := 1 to M
for j := 1 to M
array fib[1..max(2, N)]
fib[1] := A[i]
fib[2] := B[j]
for k := 3 to N
fib[k] := fib[k-1] + fib[k-2]
result := result + fib[N]

Compute the final value of the variable result. Since it can be very large, compute its remainder modulo $10^{9}+7$.

------ Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains two space-seperated integers $M$ and $N$.
The second line contains $M$ space-seperated integers $A_{1}, A_{2}, \dots, A_{M}$.
The third line contains $M$ space-seperated integers $B_{1}, B_{2}, \dots, B_{M}$.

------ Output ------
For each test case, print the final value of result modulo $10^{9}+7$.

------ Constraints ------
$1 ≤ T ≤ 10$
$1 ≤ M ≤ 10^{5}$
$1 ≤ N ≤ 10^{5}$
$0 ≤ A_{i}, B_{i} ≤ 10^{9}$ for each valid $i$

------ Subtasks ------
Subtask #1 (20 points): $1 ≤ N, M ≤ 100$

Subtask #2 (80 points): original constraints

----- Sample Input 1 ------
1
3 3
1 2 3
4 5 6
----- Sample Output 1 ------
63
----- explanation 1 ------
Example case 1: The innermost loop is ran for 9 pairs of initial values: $(1,4), (1,5), (1,6), (2,4), (2,5), (2,6), (3,4), (3,5), (3,6)$. The corresponding values added to result are
$5, 6, 7, 6, 7, 8, 7, 8, 9$, and their sum is 63.

见题面

见题面