# Need for sum thing

You are given a triangle table of N lines. First line consists of one element, second line of three, third of ve and so on. ith line consists of 2i-1 elements. Central elements of all lines are in same coloum. So, lines form an isosceles triangle.

Each element of triangle is a number from '0' to '9'.

Problem is to respond queries with sums of elements of some triangle region of original table. Each request has a form like:

r_i, c_i, k_i

meaning that triangle of ith request has k_i lines, rst line consists of one element (r_i, c_i):

Second ine of three elements (r_i+1, c_i), (r_i+1, c_i+1), (r_i+1, c_i+2), third of ve and so on.

Find sum of all the elements from the request.

Because of a great number of queries, they are generated programmly:

A_1 = 1

A_i = (1234567·A_{i-1} + 7654321) mod 1000000007, при 2 ≤ i ≤ Q

r_i = A_i mod N + 1

c_i = A_i mod (2r_{i }- 1) + 1

k_i = A_i mod (n - r_{i }+ 1) + 1

## Input

In the first line N and Q are size of original triangle and amount of requests. Then table is de ned in N lines. ith of them has exactly 2i-1 numbers, which are elements of table.

## Output

Because of great number of requests, output sum of all the reports to requests.

Limits

1 ≤ N ≤ 10^3

0 ≤ Q ≤ 5·10^6