题目描述

三十季之后，玛吉·辛普森终于上了一年级。为了练习书写，老师要求孩子们按某种顺序写下 $N$ 个数字，数字来自 0 到 9。

经过几个小时的痛苦努力，玛吉终于完成作业，跑去和朋友们玩了，把作业本留在书桌上。这时，丽莎·辛普森走进房间。萨克斯吹得有些累的她正在寻找新的有趣事情，目光停在了玛吉写满数字的本子上。

丽莎很快算出了玛吉写下的所有数字之和。这时巴特冲进房间，给了她一个更有趣的任务：对这串数字进行 $M$ 次操作。巴特的想象力很有限，所以操作只有两种。

设字符串位置从左到右编号为 $1$ 到 $N$。两类操作如下：

1. 巴特给出 $l_i,r_i$ 和数字 $c_i$，丽莎需要把位置 $l_i$ 到 $r_i$（含两端）的所有数字都替换为 $c_i$。

2. 巴特给出 $l_i,r_i$，丽莎需要计算：在原字符串从 $l_i$ 到 $r_i$ 的子串中，所有作为其子串出现的十进制数之和。每个数要按出现次数计入，即它的十进制表示在该区间中出现几次就加几次。只统计合法的十进制表示，因此以 0 开头的子串不计入该和。

巴特今天很善良，所以对于第二类操作，他只要求丽莎输出答案对 $10^9+7$ 取模的结果。

巴特自己并不知道正确答案，因此需要你帮忙。

输入格式

第一行包含两个整数 $N,M$，表示玛吉写下的数字个数和巴特的操作数。

第二行包含 $N$ 个数字，每个数字在 $0$ 到 $9$ 之间，以空格分隔。

接下来 $M$ 行描述操作：

• 1 li ri ci 表示第一类操作，满足 $1 \le l_i \le r_i \le N$，$0 \le c_i \le 9$；
• 2 li ri 表示第二类操作，满足 $1 \le l_i \le r_i \le N$。

输出格式

对每个第二类操作，输出一行答案对 $10^9+7$ 取模后的结果。

如果没有第二类操作，则不需要输出任何内容。

数据范围

$1 \le N,M \le 100000$。

样例

样例 1

4 3
1 2 1 3
2 1 3
1 3 3 0
2 2 4

158
228

样例 2

9 3
1 1 1 1 1 1 1 1 1
2 1 9
1 1 9 9
2 1 9

137174205
234567838

样例解释

第一个第二类操作的答案为：

第二个第二类操作的答案为：

注意其中项数较少，因为字符串 03 不是合法的十进制整数表示。

评分说明