It's time for the Potions class. Harry absolutely HATES potions because he has to face mockery by the potions teacher Snape every time he has a potions class. Snape never leaves any chance of insulting him in front of everyone.

Snape is not in a good mood today, which is not good for Harry. Snape challenges Harry to answer his question. If Harry fails to answer, he will have to spend the whole week in detention!.

He gives Harry n numbers (a1, a2, a3 ... an) and q queries. Each query will consist of four integers w, x, y, z. The result of a query is given by the following equation:

Help Harry or else he'll miss his Quidditch match against Slytherin because of his detention!!

Input

The first line of the input contains T, the number of test cases. T test cases follow.

The first line of each test case contains n and q.

The second line of each test case contains n integers (a1, a2, a3 ... an)

Each of the next q lines contain w, x, y, z.

Output

For each test case output the result as given by the equation.

The answer may be very large, so output it modulo 10⁹+7.

Constraints

1 ≤ T ≤ 10

1 ≤ n, q ≤ 10⁵

1 ≤ x+i ≤ n (for all y ≤ i ≤ z )

0 ≤ ai ≤ 10⁹ (for all 1 ≤ i ≤ n)

1 ≤ w ≤ 10⁶

0 ≤ y ≤ z

Example

Input:
1
5 2
2 1 4 7 2
1 1 0 2
1 5 0 0

Output:
16
2