P12087 [RMI 2019] 好数 / Lucky Numbers

在某些文化中，数字 $13$ 被视为霉运之兆。

**本题中下标是 $\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$ 操作输出一行一个非负整数，表示答案。

对于 $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$。 ### 子任务 | 编号 | $n\le$ | $q$ | 特殊性质 | 分值 | | :-: | :-: | :-: | :-: | :-: | | $1$ | $6$ | $=0$ | | $14$ | | $2$ | $18$ | $=0$ | | $14$ | | $3$ | $10^4$ | $\le 10^4$ | A | $9$ | | $4$ | $10^5$ | $\le 10^4$ | A | $27$ | | $5$ | $10^4$ | $\le 10^4$ | | $9$ | | $6$ | $10^5$ | $\le 10^4$ | | $27$ | 特殊性质 A：只有操作 $1$。