You are given a triangle table of \textbf{N} lines. First line consists of one element, second line of three, third of ve and so on. \textbf{i}th line consists of \textbf{2i-1} elements. Central elements of all lines are in same coloum. So, lines form an isosceles triangle. \includegraphics{https://static.e-olymp.com/content/e7/e79a2f0f0832d89da0d719dcbc23e6cba2ca48ed.jpg} Each element of triangle is a number from '\textbf{0}' to '\textbf{9}'. Problem is to respond queries with sums of elements of some triangle region of original table. Each request has a form like: \textbf{r_i, c_i, k_i} meaning that triangle of \textbf{i}th request has \textbf{k_i} lines, rst line consists of one element (\textbf{r_i}, \textbf{c_i}): \includegraphics{https://static.e-olymp.com/content/d2/d29c690651058d429d2c6d3928cb74eda91dcc96.jpg} Second ine of three elements (\textbf{r_i+1}, \textbf{c_i}), (\textbf{r_i+1}, \textbf{c_i+1}), (\textbf{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: \textbf{A_1 = 1} \textbf{A_i = (1234567·A_\{i-1\} + 7654321) mod 1000000007}, при\textbf{ 2} ≤ \textbf{ i} ≤ \textbf{Q} \textbf{r_i = A_i mod N + 1} \textbf{c_i = A_i mod (2r_\{i \}- 1) + 1} \textbf{k_i = A_i mod (n - r_\{i \}+ 1) + 1} \InputFile In the first line \textbf{N} and \textbf{Q} are size of original triangle and amount of requests. Then table is de ned in \textbf{N} lines. \textbf{i}th of them has exactly \textbf{2i-1} numbers, which are elements of table. \OutputFile Because of great number of requests, output sum of all the reports to requests. \textbf{Limits} \textbf{1} ≤ \textbf{N} ≤ \textbf{10^3} \textbf{0} ≤ \textbf{Q} ≤ \textbf{5·10^6}