Counting Valid Numbers Without the Substring 13

We are given an n-digit number x (possibly with leading zeros). We first need to compute the number of non‐negative integers less than or equal to x in decimal representation that do not contain 13 as a consecutive substring.

In addition, there are q operations. Each operation is one of the two following types:

• 1 l r: Consider x as a string and let y be the number represented by the substring xlxl+1...xr (note that y can have leading zeros). Compute the number of non‐negative integers ≤ y which do not contain the substring 13 in their decimal representation.
• 2 p d: Replace the digit at position p of x with digit d.

All answers (including the initial computation and every query of type 1) should be given modulo \(10^9+7\).

Note: In this problem, the indices are \(1\)-indexed.

inputFormat

The first line contains two integers \(n\) and \(q\) denoting the length of the number x and the number of operations, respectively.

The second line contains a string of length \(n\) representing the number x (which may contain leading zeros).

Then \(q\) lines follow, each representing an operation in one of the following formats:

• 1 l r
• 2 p d

For an operation of type 1, output the answer in a new line. For an operation of type 2 update x accordingly. Also, before processing the operations, output the answer for the initial number x in the first line.

outputFormat

For the given initial number and each operation of type 1, output a single integer in one line – the number of non-negative integers (≤ the given number) that do not contain the substring 13 in their decimal representation, modulo \(10^9+7\).

sample

3 3
120
1 1 2
2 2 3
1 1 3

119
13
128