Given an integer N and an array containing N elements. Also given an integer Q denoting the number of queries. Query consist of three integers, T, X and Y. T denotes the query type and can take values 0 and 1. X denotes the starting position of the query. Y denotes the increment in position. Type 0 is for addition and Type 1 is for multiplication. For eg: Given N = 5,

arr[] = 1 2 3 4 5

Q=2,

0 2 2

1 1 3

For first query, T=0, X=2, Y=2. So we have to return sum of arr[X] + arr[X+Y] + arr[X+2Y] till end of array. Here it would be arr[2] + arr[4] = 3+5=8

For second query, T=1, X=1, Y=3. So we have to return product of arr[X] * arr[X+Y] * arr[X+2Y] till end of array. Here, arr[1] * arr[4] = 2 * 5 =10

As the answer can be large, return ans modulo 10^9+7.

N,Q <= 10^5

arr[i] <= 10^9