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

给定一个由 $N$ 位数字组成的数 $X$。你需要计算有多少个小于或等于 $X$ 的非负整数，其十进制表示中不包含 13 作为子串。由于答案可能非常大，请输出其对 $1\,000\,000\,007$ 取模的结果。

此外，你需要处理 $Q$ 个查询，查询分为以下两种类型：

(1) Query(radixL, radixR)：计算有多少个小于或等于 substr(X, radixL, radixR) 的非负整数，其十进制表示中不包含 13 作为子串。由于答案可能非常大，请输出其对 $1\,000\,000\,007$ 取模的结果。substr(X, L, R) 表示 $X$ 从左往右数第 $L$ 位到第 $R$ 位组成的子串；

(2) Update(radix, newDigit)：替换 $X$ 的某一位数字。具体来说，将从左往右数第 radix 位数字修改为 newDigit。

注意：数 $X$ 的下标从 1 开始。 注意：数 $X$ 和 substr(X, l, r) 可能包含前导零。

输入格式

第一行包含两个整数 $N$ 和 $Q$ ($1 \le N \le 100\,000$, $0 \le Q \le 10\,000$)，分别表示数 $X$ 的位数和需要处理的查询数量。

第二行包含数 $X$。

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

如果 $t = 1$，则该行描述一个 Query，后跟两个整数 radixL 和 radixR ($1 \le radixL \le radixR \le N$)，表示你需要考虑作为查询边界的子串的左右端点。

否则 ($t = 2$)，该行描述一个 Update，后跟两个整数 radix 和 newDigit ($1 \le radix \le N$, $0 \le newDigit \le 9$)，表示需要修改的数字位置和该数字的新值。

输出格式

输出的第一行包含一个整数，表示有多少个小于或等于 $X$ 的非负整数不包含 13 作为子串。由于答案可能非常大，请输出其对 $1\,000\,000\,007$ 取模的结果。

然后，对于每个第一类查询，在单独的一行中输出对 $1\,000\,000\,007$ 取模后的答案。

子任务

(1) $1 \le N \le 6$, $Q = 0$ (14 分) (2) $1 \le N \le 18$, $Q = 0$ (14 分) (3) $1 \le N \le 10\,000$, $0 \le Q \le 10\,000$, 所有查询均为第一类 (9 分) (4) $1 \le N \le 100\,000$, $0 \le Q \le 10\,000$, 所有查询均为第一类 (27 分) (5) $1 \le N \le 10\,000$, $0 \le Q \le 10\,000$ (9 分) (6) $1 \le N \le 100\,000$, $0 \le Q \le 10\,000$ (27 分)

样例

输入 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

输出 1

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" 询问有多少个小于或等于 466461 的非负整数不包含子串 13，结果为 6228。 查询 "1 1 3" 询问有多少个小于或等于 466461 的非负整数不包含子串 13，结果为 452。 查询 "1 6 6" 询问有多少个小于或等于 466461 的非负整数不包含子串 13，结果为 2（即 0 和 1）。 查询 "1 2 6" 询问有多少个小于或等于 466461 的非负整数不包含子串 13，结果为 63454。 在更新 "2 1 7" 后，$X$ 变为 766461。