Random Function

Cover is an admin of HOJ, MUT is coming and he needs to generate passwords for every team of MUT. Thus he needs a pesudo-random number generator.

As we know, random numbers are usually gernerated by a random number table and a random seed. The random table is an large array. Using random seed to calculate a subscript, we can use the corresponding number in the talbe as a pesudo-random number.

But Cover is a geek and he won't do this as others did. He uses a circle array of length N as random table and three numbers ( a, b, c) as random seed. The random nubmer is defined as the product of table[a], table[(a+b-1)%N+1], table[(a+2b-1)%N+1] ... table[c] ( see Sample Input for more details). Of course this product P may be too large, so Cover use P % 1000000007 as the result.

Now it's your task, given the table and a query( a, b, c), help Cover find out the pesudo-random number.

Multiple test cases, at most 20. Process to the end of the file.

The first line of input contains three numbers, N, Q, (1 ≤ N ≤ 50000, 1 ≤ Q ≤ 50000) descripting the length of the circle array, the number of queries, and M mentioned above. The second line contains N positive integers less than 10^9, denotes the (1..N)th numbers of the circle array. Then comes Q lines, each line contains three number, means a query of a, b, c ( 1 ≤ a, b, c ≤ N). It's guaranteed that there's an interger i makes c = a + b * i or c + N = a + b * i;

Print Q lines for each test case, one number per line, which is the pesudo-random number.

6 5
1 2 3 4 5 6
1 1 6
1 3 1
1 3 4
2 4 6
3 5 2

720
1
4
12
6

2011 Multi-University Training Contest 13 - Host by HIT