题目背景

给定一个n个圆盘组成的汉诺塔，
这些圆盘按照大小严格递减的方式套在三根装柱中的一根上.
我们的目的是要将整个塔移动到另一根装柱上，每次只能移动一个圆盘.
且较大的圆盘中移动的过程中不能放置在较小的圆盘上面.

以上文本选自汉诺塔。

题目描述

公元10086年，一位老师教它的$n$个学生玩这个游戏，我们记学生为编号$1 - n$

游戏的规则有所不同，假设三根柱子是A,B,C，那么你只能将A上的圆盘移动到B上，B上的圆盘只能移动到C上，C上的圆盘只能移动到A上。

假设孩子都绝顶聪明，都使用最优秀的做法。

这位老师有$3$个操作：

1. 将编号为 $l$ 到 $r$ 的孩子汉诺塔层数增加 $k$
2. 将编号为 $l$ 到 $r$ 的孩子的汉诺塔改为 $k$
3. 求出编号 $l$ 到 $r$ 的孩子的步数的总数

输入格式

第一行给定孩子数量$n$ 操作数量$q$

第二行原序列$num_1-num_n$

接下来的$q$行，每行一个操作，如题目描述

输出格式

对于每个操作$3$，输出问题的答案，对$10^9+7$ 取模 (一个质数)

样例 #1

样例输入 #1

1 1
3
3 1 1

样例输出 #1

15

样例 #2

样例输入 #2

10 10
9 9 9 0 8 3 9 2 6 0
1 7 9 0
3 7 10
2 6 6 4
2 1 9 0
3 4 6
2 3 7 4
1 7 8 0
1 4 7 5
3 6 6
1 2 5 4

样例输出 #2

7019
0
6687

提示

样例一解释

用 $i$ 表示大小为 $i$ 的圆环

$A,B,C$ 表示现在的位置

最优方案为

$$1->B,1->C,2->B,1->A,2->C,1->B,1->C$$ $$3->B,1->A,1->B,2->A,1->C,2->B,1->A,1->B$$

15步。

可以证明，没有其他更优的方案。

数据范围

对于 $10\%$ 的数据 $n=1$ , $q\le 100$ ,$num_i,k\le 2$

对于另外 $10\%$ 的数据 $n=1$ , $q\le 10^5,num_i,k\le 10^2$

对于另外 $20\%$ 的数据，满足每个时刻序列中的每个数都不大于 $10^6$ ， $n\le 10^3$

对于另外 $30\%$ 的数据，没有操作1

对于 $100\%$ 的数据 $n,q\le 10^5,k\le 10^9+7$

时间限制$3s$，时间限制在std的10倍以上，保证不卡任何常数。

tips:时间限制的大小导致这题有很多做法。