题目描述

阿绫有 $2$ 个数组 $a,b$，一开始 $2$ 个数组为空数组。

阿绫会进行 $m$ 次操作，设当前数组长度为 $n$，操作有以下类型：

1. 给定 $x,c,p,q,u,v$，分别在数组 $a,b$ 的第 $x$ 个数和第 $x+1$ 个数之间插入 $c$ 个数 $(0\le x\le n)$，对于 $1\le i\le c$，在 $a$ 中插入的第 $i$ 个数为 $pq^{i-1}$，在 $b$ 中插入的第 $i$ 个数为 $u+v(i-1)$。
2. 给定 $l,r$，删除数组 $a,b$ 的区间 $[l,r]$ $(1\le l\le r\le n)$。
3. 给定 $l,r$，翻转数组 $a,b$ 的区间 $[l,r]$ $(1\le l\le r\le n)$。
4. 给定 $l,r$，询问 $\sum_{i=l}^r a_ib_i$，答案对 $P=10^9+7$ 取模 $(1\le l\le r\le n)$。
5. 给定 $l,r,u,v$，对数组 $b$ 的区间 $[l,r]$ 进行修改 $(1\le l\le r\le n)$，对于 $l\le i\le r$，将 $b_i$ 修改为 $b_i+u+v(i-l)$。

输入格式

从文件 future.in 中读入数据。

第一行 $3$ 个整数 $tid,m$，其中 $tid$ 表示测试点编号，样例中 $tid=0$。

接下来 $m$ 行，每行若干个整数表示一次操作。

对于第一种操作，输入 1 x c p q u v。
对于第二种操作，输入 2 l r。
对于第三种操作，输入 3 l r。
对于第四种操作，输入 4 l r。
对于第五种操作，输入 5 l r u v。

输出格式

输出到文件 future.out 中。

对于每次询问操作，输出一行一个整数，表达答案对 $P=10^9+7$ 取模的结果。

样例

样例输入1

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

样例输出1

370

样例解释1

第 $1$ 次操作后，序列 $a,b$ 分别为 $\{1,2,4,8,16\},\{3,7,11,15,19\}$。
第 $2$ 次操作后，序列 $a,b$ 分别为 $\{1,2,16\},\{3,7,19\}$。
第 $3$ 次操作后，序列 $a,b$ 分别为 $\{2,1,16\},\{7,3,19\}$。
第 $4$ 次操作后，序列 $a,b$ 分别为 $\{2,1,16\},\{7,4,22\}$。
第 $5$ 次询问，答案为 $2\times 7 + 1\times 4 + 16\times 22=370$。

样例 2

见选手目录下的 future/future2.in 与 future/future2.ans。

这个样例满足测试点 $1\sim 2$ 的约束条件。

样例 3

见选手目录下的 future/future3.in 与 future/future3.ans。

这个样例满足测试点 $5\sim 6$ 的约束条件。

样例 4

见选手目录下的 future/future4.in 与 future/future4.ans。

这个样例满足测试点 $7\sim 8$ 的约束条件。

样例 5

见选手目录下的 future/future5.in 与 future/future5.ans。

这个样例满足测试点 $11\sim 12$ 的约束条件。

样例 6

见选手目录下的 future/future6.in 与 future/future6.ans。

这个样例满足测试点 $15\sim 16$ 的约束条件。

样例 7

见选手目录下的 future/future7.in 与 future/future7.ans。

这个样例满足测试点 $21\sim 22$ 的约束条件。

样例 8

见选手目录下的 future/future8.in 与 future/future8.ans。

这个样例满足测试点 $23\sim 25$ 的约束条件。

数据范围

数据范围中变量含义与题目描述一致，$n$ 的范围表示任意时刻数组长度的范围。

对于 $100\%$ 的数据，$1\le m\le 3\times 10^5$，$0\le x\le n\le 10^9$，$1\le c\le 10^9$，$1\le l\le r\le n$，$1\le p,q\lt P$，$0\le u,v\lt P$。

测试点编号	$m$	特殊限制
$1\sim 2$	$\le 5000$	$n\le 5000$
$3\sim 4$	$\le 3\times 10^5$	$ABE$
$5\sim 6$		$BE$
$7\sim 8$		$ADE$
$9\sim 10$		$AE$
$11\sim 12$		$E$
$13\sim 14$	$\le 8\times 10^4$	$AB$
$15\sim 16$		$C$
$17\sim 18$		$AD$
$19\sim 20$	$\le 3\times 10^5$	$B$
$21\sim 22$		$A$
$23\sim 25$		无

特殊限制 $A$: 不存在操作 $3$。
特殊限制 $B$: 不存在操作 $5$。
特殊限制 $C$: 保证 $q=1$。
特殊限制 $D$: 保证 $v=0$。
特殊限制 $E$: 保证 $\sum c\le m$。