说明

时间限制：2s 内存限制：256

输入文件：fin.in,输出文件：fib.out

给定一个长度为 $N$ 的序列 $a_0,a_1,\ldots,a_{N-1}$，初始时所有 $a_i=0$。

你需要处理 $Q$ 个询问，每个询问 $4$ 个参数 $(q,l,r,k)$，含义如下：

- 当 $q=0$ 时：计算 $k \times \sum_{i=l}^{r}a_i$ 的结果，对 $10^9+7$ 取余后输出，输出后换行。

- 当 $q=1$ 时：对所有满足 $l \leq i \leq r$ 的下标 $i$，将 $a_i$ 的值修改为 $k$。

- 当 $q=2$ 时：对所有满足 $l \leq i \leq r$ 的下标 $i$，将 $a_i$ 的值更新为 $a_i + k$。

- 当 $q=3$ 时：对所有满足 $l \leq i \leq r$ 的下标 $i$，将 $a_i$ 的值更新为 $a_i \times k$。

- 当 $q=4$ 时：对所有满足 $l \leq i \leq r$ 的下标 $i$，将 $a_i$ 的值更新为 $a_i + k \times F_i$。

其中，$\{F_n\}$ 表示斐波那契数列，满足 $F_0=0$、$F_1=1$，且对于 $n \geq 2$，有 $F_n = F_{n-1} + F_{n-2}$。

输入格式

第一行 $2$ 个整数 $N,Q$。

接下来 $Q$ 行，每行 $4$ 个整数 $q,l,r,k$ 表示一个询问。

输出格式

对于每个 $q=0$ 的询问，输出一行，一个整数表示答案。

样例

样例 1

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

38

样例 2

1000000 20
4 359471 684726 491381080
1 409194 601926 917565989
0 135463 321888 288655811
0 394349 521374 932477099
4 399576 593770 745147335
0 4942 864793 41822405
1 829464 948381 376118299
0 436494 767172 738319909
3 121220 700989 148573041
0 139030 302916 790535508
4 707671 790846 877035358
0 28809 102020 969776242
2 439930 622579 490581891
0 404296 961224 251978919
4 613570 750113 563397295
1 50064 717205 790676632
3 249673 934546 400250755
2 302615 388704 165894970
4 10286 930329 517008122
4 784365 959138 63130254

0
775465869
711055457
444030161
0
0
403409237

数据范围

20%: $N\leq 10,Q\leq 10$

40%：$N\leq 10^3,Q\leq 10^3$

100%：$1\leq N\leq 10^6,1\leq Q\leq 10^5,q_i\in\{0,1,2,3,4\},0\leq l_i\leq r_i< N,0\leq k\leq 10^9$