Maggie's Homework

Maggie Simpson has finally started first grade after thirty seasons. For handwriting practice, the teacher asked the children to write N digits from 0 to 9 in a row, in any order.

After hours of effort, Maggie finished the homework and ran off to play with her friends, leaving the paper on the desk. Lisa Simpson walked into the room and noticed the notebook.

Lisa quickly found the sum of all the digits Maggie wrote. Then Bart came in with a harder task: perform M operations on this digit string. Positions are numbered from 1 to N, left to right. There are two types of operations.

1 $l_i$ $r_i$ $c_i$: replace every digit at positions $l_i$ through $r_i$ with the digit $c_i$.

2 $l_i$ $r_i$: compute the sum of all numbers whose decimal representations occur as substrings of the segment from position $l_i$ through $r_i$. Each number is counted as many times as its representation occurs in the segment. Substrings that begin with '0' are not included in the sum. Output the answer modulo $10^9 + 7$.

The first line contains two integers N and M separated by a space, the number of digits and the number of Bart's operations ($1 \le N, M \le 100000$).

The second line contains N digits from 0 to 9, separated by spaces.

Each of the next M lines describes an operation. A line 1 $l_i$ $r_i$ $c_i$ is a first-type operation with $1 \le l_i \le r_i \le N$ and $0 \le c_i \le 9$. A line 2 $l_i$ $r_i$ is a second-type operation with $1 \le l_i \le r_i \le N$.

For each operation of the second type, print the answer modulo $10^9 + 7$ on its own line. If there are no operations of the second type, print nothing.

In the first sample, the answer to the first type-2 operation is $1 + 12 + 121 + 2 + 21 + 1 = 158$. The answer to the second is $2 + 20 + 203 + 0 + 3 = 228$. That sum has fewer terms because 03 is not a valid decimal representation of an integer.