Пусть есть треугольная таблица из \textbf{N} строк. Первая строка таблицы состоит из одного элемента, вторая строка --- из трёх, третья --- из пяти и т.д. \textbf{i}-тая строка состоит из \textbf{2i-1} элемента. Средние элементы всех строк образуют один столбец. Таким образом, таблица представляет собой равнобедренный прямоугольный треугольник. В верхнем элементе таблицы находится прямой угол, а в нижней строке --- гипотенуза. \includegraphics{https://static.e-olymp.com/content/e7/e79a2f0f0832d89da0d719dcbc23e6cba2ca48ed.jpg} Каждый элемент таблицы --- некоторая цифра от '\textbf{0}' до '\textbf{9}'. Требуется ответить на \textbf{Q} запросов суммы всех элементов некоторой треугольной области исходной таблицы. Каждый запрос имеет вид: \textbf{r_i, c_i, k_i} Область \textbf{i}-того запроса представляет собой равнобедренный прямоугольный треугольник из \textbf{k_i} строк с вершиной в (\textbf{r_i}, \textbf{c_i}): \includegraphics{https://static.e-olymp.com/content/d2/d29c690651058d429d2c6d3928cb74eda91dcc96.jpg} Первая строка состоит из элемента (\textbf{r_i}, \textbf{c_i}). Вторая строка --- из трёх элементов: (\textbf{r_i+1}, \textbf{c_i}), (\textbf{r_i+1}, \textbf{c_i+1}), (\textbf{r_i+1, c_i+2}), третья из пяти и т.д. Нужно найти сумму всех элементов треугольника из запроса. Поскольку запросов много, они генерируются программно: \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 В первой строке \textbf{N} и \textbf{Q} --- количество строк исходного треугольника и количество запросов. Далее в \textbf{N} строках идёт описание таблицы. В \textbf{i}-той из них ровно \textbf{2i-1} цифр --- элементы таблицы (между цифрами нет пробелов). \OutputFile Поскольку запросов много, выведите одно число --- сумму всех ответов на запросы. \textbf{Ограничения} \textbf{1} ≤ \textbf{N} ≤ \textbf{10^3} \textbf{0} ≤ \textbf{Q} ≤ \textbf{5·10^6} \textbf{^\{ \}Пояснение} \includegraphics{https://static.e-olymp.com/content/ae/ae67640ff8f1a37591c312d8fff3cdbeea377d50.jpg} Исходный треугольник: \includegraphics{https://static.e-olymp.com/content/99/992d6869aa0e7230406d58321b6e3e2c837ae1be.jpg} Первый запрос: , сумма \textbf{24}. Второй запрос: \textbf{8}, сумма \textbf{8}. Третий запрос: \textbf{6}, сумма \textbf{6}. Четвертый запрос: \textbf{1}, сумма \textbf{1}. Пятый запрос: \textbf{3}, сумма \textbf{3}.