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

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

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

• Барт называет два числа \(l_i\) и \(r_i\), а также цифру \(c_i\), после чего Лиза должна заменить все цифры на позициях с \(l_i\)-й по \(r_i\)-ю включительно на цифру \(c_i\).
• Барт называет два числа \(l_i\) и \(r_i\), после чего Лиза должна посчитать сумму всех чисел, десятичные записи которых встречаются как подстроки отрезка исходной строки с \(l_i\)-й по \(r_i\)-ю позицию включительно. При этом каждое число должно быть просуммировано с учётом кратности, то есть столько раз, сколько его запись встречается на отрезке с \(l_i\)-й по \(r_i\)-ю. Также требуется учитывать только корректные десятичные записи чисел, то есть подстроки, начинающиеся на `\(0\)', не должны входить в сумму.

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

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

Входные данные

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

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

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

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

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

Выходные данные

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

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

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