Домашнее задание

문제

Спустя тридцать сезонов Мэгги Симпсон наконец поступила в первый класс. В целях тренировки чистописания учительница задала детям выписать в строку N цифр от ‘0’ до ‘9’ в некотором порядке.

После нескольких часов страданий Мэгги всё-таки справилась с домашним заданием и убежала играть с друзьями, оставив свою работу лежащей на письменном столе. В это время в комнату зашла Лиза Симпсон. Игра на саксофоне уже успела её порядком утомить, и она находилась в поисках какого-нибудь нового увлекательного занятия, когда её взгляд остановился на исписанной тетрадке Мэгги.

Лиза быстро справилась с тем, чтобы посчитать сумму всех написанных Мэгги цифр, но тут в комнату ворвался Барт и предложил ей задачу поинтереснее — произвести M операций с данной строкой цифр. Фантазия Барта довольно скудна, поэтому операции бывают только двух типов. Пусть позиции в строке занумерованы числами от 1 до N слева направо. Тогда операции имеют следующий вид:

1. Барт называет два числа l_i и r_i, а также цифру c_i, после чего Лиза должна заменить все цифры на позициях с l_i-й по r_i-ю включительно на цифру c_i.
2. Барт называет два числа l_i и r_i, после чего Лиза должна посчитать сумму всех чисел, десятичные записи которых встречаются как подстроки отрезка исходной строки с l_i-й по ri-ю позицию включительно. При этом каждое число должно быть просуммировано с учётом кратности, то есть столько раз, сколько его запись встречается на отрезке с l_i-й по r_i-ю. Также требуется учитывать только корректные десятичные записи чисел, то есть подстроки, начинающиеся на ‘0’, не должны входить в сумму.

Барт сегодня добрый, поэтому на операцию второго типа он просит от Лизы только остаток от деления ответа на 10⁹ + 7.

Желая доказать своё превосходство над братом, Лиза немедленно согласилась. Поскольку Барт сам не знает правильных ответов, он никак не может проверить вычисления Лизы, поэтому ему крайне необходима ваша помощь.

입력

В первой строке ввода записаны через пробел два целых числа N и M — количество цифр, выписанных Мэгги, и количество операций Барта (1 ⩽ N, M ⩽ 100 000).

Вторая строка ввода содержит N цифр от 0 до 9, разделённых пробелами.

Следующие M строк описывают операции.

Запись вида 1 l_i r_i c_i обозначает операцию первого типа (1 ⩽ l_i ⩽ r_i ⩽ N, 0 ⩽ c_i ⩽ 9).

Запись вида 2 l_i r_i обозначает операцию второго типа (1 ⩽ l_i ⩽ r_i ⩽ N).

출력

На каждую операцию второго типа выведите остаток от деления ответа на 10⁹ + 7.

Если среди операций Барта не присутствует ни одной операции второго типа, ничего выводить не требуется.

힌트

На первую операцию второго типа ответ представляет собой следующую сумму: 1 + 12 + 121 + 2 + 21 + 1 = 158.

На вторую операцию второго типа ответ представляет собой следующую сумму: 2 + 20 + 203 + 0 + 3 = 228. Обратите внимание: в ней присутствует меньше слагаемых, так как строка 03 не представляет собой корректную десятичную запись целого числа.

4 3
1 2 1 3
2 1 3
1 3 3 0
2 2 4

158
228

9 3
1 1 1 1 1 1 1 1 1
2 1 9
1 1 9 9
2 1 9

137174205
234567838