题目描述

题目译自 Romanian Master of Informatics 2019 Day1 T2 「Lucky Numbers」

众所周知，在某些文化中，数字 $13$ 被认为会带来厄运。

现在，给你一个由 $N$ 个数字组成的数字 $X$。你需要计算出有多少个小于或等于 $X$ 的数字，在它们的十进制表示中不包含子字符串 $13$。由于答案可能会非常大，你需要将结果对 $1000000007$ 取模。

此外，你还需要处理 $Q$ 个操作，操作分为两种类型：

1. $\texttt{Query(radixL, radixR)}$：计算有多少个小于或等于子字符串 $\texttt{substr(X, radixL, radixR)}$ 的数字，在十进制表示中不包含子字符串 $13$。同样，由于答案可能很大，结果需对 $1000000007$ 取模。这里，$\texttt{substr(X, L, R)}$ 表示 $X$ 从从左到右第 $L$ 个数字开始到第 $R$ 个数字结束的子字符串。
2. $\texttt{Update(radix, newDigit)}$：将 $X$ 的某个数字修改掉。具体来说，将从左到右第 $\texttt{radix}$ 个数字改为 $\texttt{newDigit}$。

注意：数字 $X$ 的索引从 $1$ 开始。

注意：数字 $X$ 及其子字符串 $\texttt{substr(x, l, r)}$ 可能包含前导零。

输入格式

输入的第一行包含两个整数 $N$ 和 $Q$ $(1 \leq N \leq 10^5, 0 \leq Q \leq 10^4)$，分别表示数字 $X$ 的位数和你需要处理的操作数量。

第二行输入数字 $X$。

接下来的 $Q$ 行描述需要处理的查询。每行以一个整数 $t$ $(1 \leq t \leq 2)$开头，表示操作的类型：

• 如果 $t=1$，则该行描述一个查询，后面跟着两个整数 $\texttt{radixL}$ 和 $\texttt{radixR}$ $(1 \leq \texttt{radixL} \leq \texttt{radixR} \leq N)$，表示你需要考虑的子字符串的左右边界。
• 如果 $t=2$，则该行描述一个更新，后面跟着两个整数 $\texttt{radix}$ 和 $\texttt{newDigit}$ $(1 \leq \texttt{radix} \leq N, 0 \leq \texttt{newDigit} \leq 9)$，表示需要更改的数字位置和新值。

输出格式

输出的第一行包含一个整数，表示有多少个小于或等于 $X$ 的非负整数，在十进制表示中不包含子字符串 $13$。由于答案可能很大，需对 $1000000007$ 取模。

然后，对于每个类型 $1$ 的查询，在单独一行中输出答案，并对 $1000000007$ 取模。

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

样例中有 $528145$ 个小于或等于 560484 的非负整数，其十进制表示中不包含子字符串 $13$。注意，这包括数字 $0$。

• 初始时，$X$ 为 560484。
• 修改 2 6 4 后，$X$ 变为 560484。
• 修改 2 1 4 后，$X$ 变为 460484。
• 修改 2 5 6 后，$X$ 变为 460464。
• 修改 2 6 1 后，$X$ 变为 460461。
• 修改 2 3 6 后，$X$ 变为 466461。
• 查询 1 3 6 要求计算小于或等于 $6461$ 的非负整数中有多少个不含子字符串 $13$，结果为 $6228$。
• 查询 1 1 3 要求计算小于或等于 $466$（前三位）的不含 13 的非负整数数量，结果为 $452$。
• 查询 1 6 6 要求计算小于或等于 $1$（第 $6$ 位）的非负整数中不含 $13$ 的数量，结果为 $2$（即 $0$ 和 $1$）。
• 查询 1 2 6 要求计算小于或等于 $66461$（第 $2$ 到 $6$ 位）的非负整数中不含 $13$ 的数量，结果为 $63454$。
• 修改 2 1 7 后，$X$ 变为 766461。

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
$1$	$1 \leq N \leq 6, Q=0$	$14$
$2$	$1 \leq N \leq 18, Q=0$	$14$
$3$	$1 \leq N \leq 10^4,0 \leq Q \leq 10^4$，所有操作均为类型 1	$9$
$4$	$1 \leq N \leq 10^5,0 \leq Q \leq 10^4$，所有操作均为类型 1	$27$
$5$	$1 \leq N \leq 10^4,0 \leq Q \leq 10^4$	$9$
$6$	$1 \leq N \leq 10^5,0 \leq Q \leq 10^4$	$27$