Problem Statement

Given a sequence $\{a_i\}_{i=0}^{N-1}$ of length $N$ with all elements initialized to $0$, process $Q$ queries.

Input

$N$ $Q$
$q_1$ $l_1$ $r_1$ $k_1$
...
$q_Q$ $l_Q$ $r_Q$ $k_Q$

$1\leq N\leq 10^6$
$0\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$
All inputs are integers.

The meaning of a query $(q,l,r,k)$ is as follows.
When $q=0$: output $k\sum_{i=l}^{r}a_i$ modulo $\mod 10^9+7$, followed by a newline.
When $q=1$: for all $i$ such that $l\leq i\leq r$, change $a_i$ to $k$.
When $q=2$: for all $i$ such that $l\leq i\leq r$, change $a_i$ to $a_i+k$.
When $q=3$: for all $i$ such that $l\leq i\leq r$, change $a_i$ to $a_i*k$.
When $q=4$: for all $i$ such that $l\leq i\leq r$, change $a_i$ to $a_i+k*F_i$.
Here, $\{F_n\}$ is the Fibonacci sequence, with $F_0=0,\ F_1=1,\ F_n=F_{n-1}+F_{n-2} (n\geq 2)$.


There are 20 test cases in total.
Of these, 10 cases satisfy $N\leq 10^3$ and $Q\leq 10^3$. (About ★2)

Output

Process the queries.

Sample

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

38

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