乔帝要规划一次星际旅行，星际空间可以视为一个 $3$ 维坐标系，乔帝有 $n(n \le 10^9)$ 个动力装置排成一行(下标从 $1$ 到 $n$)。

第 $i$ 个动力装置可以让他的飞船 $3$ 个维度的坐标分别增加 $x_i,y_i,z_i$。

一开始这些动力装置的所有参数都是 $0$。

在规划过程中，乔帝可能会对动力装置进行调整，也可能会对一些动力装置的动力进行评估。

具体来说，乔帝会进行 $m(m \le 40000)$ 次操作，每次操作可能是以下四种操作之一：

• 动力增加：指定一个区间 $[L,R]$ 和三个参数 $a,b,c$，令区间内所有动力装置的 $3$ 维坐标分别增加 $a,b,c$
• 动力强化：指定一个区间 $[L,R]$ 和一个参数 $k$，令区间内所有动力装置的 $3$ 维坐标分别乘 $k$
• 动力转向：指定一个区间 $[L,R]$ ，令区间内所有动力装置的 $x,y,z$ 坐标分别变为原来的 $y$ 坐标，$z$ 坐标，$x$ 坐标
• 动力查询：指定一个区间 $[L,R]$ ，询问如果使用区间内所有动力装置各一次能将乔帝送到离起点多远的地方(输出距离的平方除以 $10^9+7$ 的余数)

输入格式

第一行包含两个正整数 $n,m$。

接下来 $m$ 行，每行用若干个空格分隔的整数表示一个操作。

每行的第一个整数表示这次进行的是哪一种操作，$1,2,3,4$ 分别表示动力增加、动力强化、动力转向、动力查询。

每行的接下来两个整数表示 $L,R$，含义如上面所述。

每行接下来若干个整数，根据操作类型确定，为 $a,b,c$ 或 $k$ 或空。

输出格式

对于每个动力查询操作，输出一行，包含一个整数，表示查询的答案。

数据范围

对于 $20\%$ 的数据，$n,m \le 1000$；
对于另外 $20\%$ 的数据，$n \le 10^5$，且只包含第 $1,4$ 种操作；
对于另外 $20\%$ 的数据，$n \le 10^5$，且只包含第 $1,2,4$ 种操作；
对于另外 $20\%$ 的数据，$n \le 10^5$；
对于另外 $20\%$ 的数据，没有特殊性质。
所有输入的数字都在 $[1,10^9]$ 范围内。
所有的数据中 $1 \le m \le 40000$，$1 \le n \le 10^9$。
所有的操作满足 $1 \le L \le R \le n$。

输入样例：

5 5
1 2 4 5 6 7
3 5 5
2 1 2 4
4 1 3
4 2 5

输出样例：

2750
3960

样例解释

一共有 $5$ 个动力装置。

对于第 $1$ 个操作，令第 $2,3,4$ 个动力装置的动力变为 $(5,6,7)$。

对于第 $2$ 个操作，令第 $5$ 个动力装置转向，为 $(0,0,0)$。

对于第 $3$ 个操作，令第 $1,2$ 个动力装置变为原来的 $4$ 倍，第一个变为 $(0,0,0)$，第二个变为 $(20,24,28)$。

对于第 $4$ 个操作，是查询，送到离起点 $(0+20+5,0+24+6,0+28+7)$，距离的平方为 $2750$。

对于第 $5$ 个操作，也是查询，送到离起点 $(20+5+5+0,24+6+6+0,28+7+7+0)$，距离的平方为 $3960$。