题目描述

本题中下标是 $\texttt{1-indexed}$ 的。

给定一个 $n$ 位数 $x$。你需要计算不大于 $x$ 的非负整数中，有多少非负整数在十进制表示下不含 $13$ 作为（连续）子串。

额外地，有 $q$ 次操作：

• $\texttt{1}$ $l$ $r$：将 $x$ 视为字符串，将 $x$ 的子串 $x_lx_{l+1}\ldots x_r$ 视为数字 $y$（$y=\overline{x_lx_{l+1}\ldots x_r}$）。计算不大于 $y$ 的非负整数中，有多少非负整数在十进制表示下不含 $13$ 作为（连续）子串。

• $\texttt{2}$ $p$ $d$：将 $x$ 的第 $p$ 位替换成 $d$。

以上所有操作答案对 $(10^9+7)$ 取模。

注意 $x$ 和 $y$ 可能有前导零。所有的答案都要对 $(10^9+7)$ 取模。

输入格式

第一行，两个整数 $n,q$。

第二行，非负整数 $x$。

接下来 $q$ 行，每行三个非负整数描述一个操作，格式见上。

输出格式

所有的答案都要对 $(10^9+7)$ 取模。

第一行，输出一个非负整数，表示不大于 $x$ 的非负整数中，有多少非负整数在十进制表示下不含 $13$ 作为子串。

接下来，对于每个 $1$ 操作输出一行一个非负整数，表示答案。

输入样例

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

输出样例

528145
6228
452
2
63454

说明提示

子任务

输入样例 #2

1 0
7

输出样例 #2

8

输入样例 #3

6 0
349434

输出样例 #3

325354

数据范围

对于 $100\%$ 的数据，保证：

• $1\le n\le 10^5$；

• $0\le q\le 10^4$；

• $1\le l\le r\le n$；

• $1\le p\le n$，$0\le d\le 9$。

特殊性质 A：只有操作 $1$。