题目描述
题目译自 Romanian Master of Informatics 2019 Day1 T2 「Lucky Numbers」
众所周知，在某些文化中，数字 13 被认为会带来厄运。
现在，给你一个由 N 个数字组成的数字 X。你需要计算出有多少个小于或等于 X 的数字，在它们的十进制表示中不包含子字符串 13。由于答案可能会非常大，你需要将结果对 1000000007 取模。
此外，你还需要处理 Q 个操作，操作分为两种类型：
- Query(radixL, radixR)：计算有多少个小于或等于子字符串 substr(X, radixL, radixR) 的数字，在十进制表示中不包含子字符串 13。同样，由于答案可能很大，结果需对 1000000007 取模。这里，substr(X, L, R) 表示 X 从从左到右第 L 个数字开始到第 R 个数字结束的子字符串。
- Update(radix, newDigit)：将 X 的某个数字修改掉。具体来说，将从左到右第 radix 个数字改为 newDigit。
注意：数字 X 的索引从 1 开始。
注意：数字 X 及其子字符串 substr(x, l, r) 可能包含前导零。
输入格式
输入的第一行包含两个整数 N 和 Q (1≤N≤105, 0≤Q≤104)，分别表示数字 X 的位数和你需要处理的操作数量。
第二行输入数字 X。
接下来的 Q 行描述需要处理的查询。每行以一个整数 t (1≤t≤2)开头，表示操作的类型：
- 如果 t=1，则该行描述一个查询，后面跟着两个整数 radixL 和 radixR (1≤radixL≤radixR≤N)，表示你需要考虑的子字符串的左右边界。
- 如果 t=2，则该行描述一个更新，后面跟着两个整数 radix 和 newDigit (1≤radix≤N, 0≤newDigit≤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 |
14 |
1≤N≤6,Q=0 |
| 2 |
1≤N≤18,Q=0 |
| 3 |
9 |
1≤N≤104,0≤Q≤104，所有操作均为类型 1 |
| 4 |
27 |
1≤N≤105,0≤Q≤104，所有操作均为类型 1 |
| 5 |
9 |
1≤N≤104,0≤Q≤104 |
| 6 |
27 |
1≤N≤105,0≤Q≤104 |
