题目描述

有一个整数 $A=\overline{a_1a_2\cdots a_n}$。

称 $x=\overline{x_1x_2\cdots x_k}$ 是关于序列 $p=\{p_1,p_2,\cdots,p_k\}$ 的生成数字，当且仅当 $\forall 1 \le i \le k,x_i=a_{p_i}$，可以证明 $x$ 唯一。这个数记为 $\operatorname{Z}(p)$。这里 $x$ 可以有前导 $0$。

有 $q$ 次操作，每次操作为下面两项之一：

1. $\texttt{M} \ x \ y \ k$：$\forall x \le i \le y$，修改 $a_i$ 为 $k$。保证 $1 \le x \le y \le n,0 \le k \le 9$。
2. $\texttt{Q} \ x \ y \ k$：询问有多少 $L=\{x,x+1,\cdots,y\}^k$ 的非空子序列 $p$ 使得 $3 \mid \operatorname{Z}(p)$？注意：即使两个子序列本质相同，但取出的位置不同，仍被记为不同的子序列。答案对 $10^9+7$ 取模，保证 $1 \le x \le y \le n，1 \le k \le 10^9$。

对于序列 $L$，$L^k$ 被定义为 $L$ 重复 $k$ 次得到的序列。如 $\{1,3\}^3=\{1,3,1,3,1,3\}$。

输入格式

第 $1$ 行，$2$ 个整数 $n,q$。
第 $2$ 行，一个 $n$ 位整数 $A$。可以有前导 $0$。
接下来 $q$ 行，每行一个操作。

输出格式

对于每个形如 $\texttt{Q} \ x \ y \ k$ 的操作，输出一行一个整数，表示答案。答案对 $10^9+7$ 取模。

样例

3 3
234
Q 1 3 1
M 2 2 8
Q 2 3 2

3
5

数据范围

对于 $100\%$ 的数据，$1 \le n,q \le 2\times10^5$。

记所有形如 $\texttt{Q} \ x \ y \ k$ 操作中，$k$ 的最大值为 $k_{\max}$。