Lucky Numbers

It's a well known fact that in some cultures the number $13$ brings bad luck.

Task

You are given a number $X$ consisting of $N$ digits. You are to compute how many numbers smaller than or equal to $X$ don't contain $13$ as a substring in their base $10$ representation. Since the answer can be quite large, you are to print it modulo $1 \ 000 \ 000 \ 007$.

In addition, you are to process $Q$ queries of two possible types:

• Query(radixL, radixR): you are to compute how many numbers smaller than or equal to $substr(X, radixL, radixR)$ don't contain $13$ as a substring in their base $10$ representation. Since the answer can be quite large, you are to print it modulo $1 \ 000 \ 000 \ 007. \ substr(X, L, R)$ stands for the substring of $X$ starting from the $L$-th digit and ending with the $R$-th digit counting from left to right
• Update(radix, newDigit): one of $X$'s digits is replaced. In particular, digit numbered $radix$ counting from left to right is changed to $newDigit$.

Input data

The first line of input contains two integers $N$ and $Q$ - the number of digits of number $X$ and the number of queries that need to be processed.

The second line of input contains the number $X$.

The next $Q$ lines describe the queries that need to be processed. Each line starts with an integer $t$ - the type of query that needs to be processed.

If $t = 1$ , then the line describes a $Query$ and two integers $radixL$ and $radixR$ follow - the left and right ends of the substring that you need to consider as bounds for the query.

Otherwise $(t = 2)$, the line describes an Update and two integers $radix$ and $newDigit$ follow - the position of the digit that needs to be changed and the new value of the digit.

Output data

The first line of the output contains a single integer - how many numbers smaller than or equal to $X$ don't contain $13$ as a substring in their base $10$ representation. Since the answer can be quite large, you are to print it modulo $1 \ 000 \ 000 \ 007$.

Then, for each query of the first type, print the answer modulo $1 \ 000 \ 000 \ 007$ on a separate line.

Constraints and clarifications

• $1 \leq N \leq 100 \ 000$
• $0 \leq Q \leq 10 \ 000$
• $1 \leq t \leq 2$
• If $t = 1$ then $1 \leq radixL \leq radixR \leq N$
• If $t = 2$, then $1 \leq radix \leq N, \ 0 \leq newDigit \leq 9$

Example

stdin

6 10
560484
2 6 4
2 1 4
2 5 6
2 6 1
2 3 6
1 3 6
1 1 3
1 6 6
1 2 6
2 1 7

stdout

528145
6228
452
2
63454

Explanation

There are $528145$ non-negative integers smaller than or equal to $560484$ not containing digits $13$ as a substring in their base $10$ representation. Note that this includes the number $0$.

• $X$ is initially $560 \ 484$.
• After update 2 6 4, $X$ becomes $56048\fbox{4}$.
• After update 2 1 4, $X$ becomes $\fbox{4}60484$.
• After update 2 5 6, $X$ becomes $4604\fbox{6}4$.
• After update 2 6 1, $X$ becomes $46046\fbox{1}$.
• After update 2 3 6, $X$ becomes $46\fbox{6}461$.
• Query 1 3 6 asks us how many non-negative integers smaller than or equal to $\cancel{46} 6461$ don't contain substring $13$ - there are $6228$ such numbers.
• Query 1 1 3 asks us how many non-negative integers smaller than or equal to $466\cancel{461}$ not containing substring $13$ - there are $452$ such numbers.
• Query 1 6 6 asks us how many non-negative integers smaller than or equal to $\cancel{46646} 1$ not containing substring $13$ - there are $2$ such numbers: $0$ and $1$.
• Query 1 2 6 asks us how many non-negative integers smaller than or equal to $\cancel{4} 66461$ not containing substring $13$ - there are $63454$ such numbers.
• After update 2 1 7, $X$ becomes $\fbox{7} 66461$.