Need for sum thing
Пусть есть треугольная таблица из N строк. Первая строка таблицы состоит из одного элемента, вторая строка — из трёх, третья — из пяти и т.д. i-тая строка состоит из 2i-1 элемента. Средние элементы всех строк образуют один столбец. Таким образом, таблица представляет собой равнобедренный прямоугольный треугольник. В верхнем элементе таблицы находится прямой угол, а в нижней строке — гипотенуза.
Каждый элемент таблицы — некоторая цифра от '0' до '9'.
Требуется ответить на Q запросов суммы всех элементов некоторой треугольной области исходной таблицы. Каждый запрос имеет вид:
r_i, c_i, k_i
Область i-того запроса представляет собой равнобедренный прямоугольный треугольник из k_i строк с вершиной в (r_i, c_i):
Первая строка состоит из элемента (r_i, c_i). Вторая строка — из трёх элементов: (r_i+1, c_i), (r_i+1, c_i+1), (r_i+1, c_i+2), третья из пяти и т.д.
Нужно найти сумму всех элементов треугольника из запроса.
Поскольку запросов много, они генерируются программно:
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
Входные данные
В первой строке N и Q — количество строк исходного треугольника и количество запросов. Далее в N строках идёт описание таблицы. В i-той из них ровно 2i-1 цифр — элементы таблицы (между цифрами нет пробелов).
Выходные данные
Поскольку запросов много, выведите одно число — сумму всех ответов на запросы.
Ограничения
1 ≤ N ≤ 10^3
0 ≤ Q ≤ 5·10^6
^{ }Пояснение
Исходный треугольник:
Первый запрос: , сумма 24.
Второй запрос: 8, сумма 8.
Третий запрос: 6, сумма 6.
Четвертый запрос: 1, сумма 1.
Пятый запрос: 3, сумма 3.