Спустя тридцать сезонов Мэгги Симпсон наконец поступила в первый класс. В целях тренировки чистописания учительница задала детям выписать в строку 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 -й по r _i -ю позицию включительно. При этом каждое число должно быть просуммировано с учётом кратности , то есть столько раз, сколько его запись встречается на отрезке с l _i -й по r _i -ю. Также требуется учитывать только корректные десятичные записи чисел, то есть подстроки, начинающиеся на ' 0 ', не должны входить в сумму.

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

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