Its time for the Potions class. Harry absolutely HATES potions because he has to face mockery by the potions teacher Snape everytime 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^9+7

Constraints:

1 ≤ T ≤10

1 ≤ n, q ≤10^5

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

0 ≤ ai ≤10^9 ( for all 1 ≤ i ≤ n )

1 ≤ w ≤10^6

0<y ≤ z

Problem Setter: Abhinav Sharma

SAMPLE INPUT
1
5 2
2 1 4 7 2
1 1 0 2
1 5 0 0

SAMPLE OUTPUT
16
2
import sys
t=int(sys.stdin.readline())
while t:
	n,q=map(int,sys.stdin.readline().split())
	s=raw_input().split()
	cum=[]
	cum2=[]
	for i in range(0,n+1):
		cum.append(0)
		cum2.append(0)
	for i in range(1,n+1):
		cum[i]=cum[i-1] + int(s[i-1])
		cum2[i]=cum2[i-1]+i*(int(s[i-1]))
	for i in range(0,q):
		w,x,y,z=map(int,sys.stdin.readline().split())
		lower = y+x
		higher = z+x
		result=(cum2[higher]-cum2[lower-1] + (w-x)*(cum[higher]-cum[lower-1]))%1000000007
		sys.stdout.write(str(result))
		sys.stdout.write("\n")
	t=t-1