POTIONS  Potions Class
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
Example
Input: 1
5 2
2 1 4 7 2
1 1 0 2
1 5 0 0
Output: 16
2
hide comments
code_aim:
20171031 17:52:20
No need of segment tree!! Easy one 

viratian_070:
20170704 16:11:58
segment tree without any optimization....nice problem 

Abhilash:
20150112 03:11:55
careful while doing modulo op


master_blaster:
20140716 22:46:02
@Abhinav92003 can you please check my code and tell the error. all test cases are working fine


you_know_why:
20140605 15:11:26
@Abhinav92003 could you please check this submission and tell me where i am going wrong....


P_Quantum:
20140525 06:40:57
Finally AC..!! 

The_ROCK:
20140523 20:26:53
correct the constraints. It is said that 0 < y <= z but in the example itself y and z both are 0.


SanchitK:
20140426 23:36:22
@adminplease can you provide a test case where i am wrong. 

Francky:
20140413 13:39:25
@psetter : please use "upload files" possibility for the image, it will prevent broken link in the future. If you need help, just ask ;) 

રચિત (Rachit):
20140413 13:39:25
@Abhinav92003, Can you please fix "Equation" image link? 
Added by:  Abhinav92003 
Date:  20140406 
Time limit:  1s5s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 