Description

华华和秀秀在玩游戏。在他们面前有球排成一排，从左到右按 $1$ 到 $n$ 编号。每个球有一个可正可负的权值。

每一轮，秀秀会选定一个区间 $[a,b]$，将编号在这个区间内的所有球的权值加上一个值 $c$ 或者将编号在这个区间内的所有球的权值都设为其相反数。

华华则需从这球中选出 $k$ 个球来，他的得分为这 $k$ 个球的权值的乘积。

华华每次都能快快地找出得分最优的选球方案来。秀秀想了想，决定提升游戏难度。她每次会选定一个区间 $[a,b]$，然后询问华华在这个区间内选出 $k(1 \le k \le 10)$ 个球的所有方案的得分之和。

这下可把华华难倒了，于是华华找到了聪明的你。你能帮帮他嘛？

由于所有方案的得分之和可能很大，你只需要输出得分之和对 $1000000007(10 ^ 9 + 7)$ 取模的结果（负数请加上 $10^9+7$ 变成非负数）即可。

Input Format

输入第一行包含两个正整数 $n,m$，分别表示球的个数和秀秀的操作条数。

接下来一行包含 $n$ 个空格隔开的整数，表示每个球初始的权值。

接下来 $m$ 行，每行表示秀秀的一个操作。

若该行形如 1 a b c，则表示将编号属于 $[a,b]$ 的所有球的权值都加上了 $c$；

若该行形如 2 a b，则表示将编号属于 $[a,b]$ 的所有球的权值都置为了其相反数；

若该行形如 3 a b k，则表示需要回答从 $[a,b]$ 中选出 $k$ 个球的所有取球方案的得分之和。

Output Format

对于每个询问操作，输出一行，表示答案。

Sample

【样例输入】

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

【样例输出】

36
999999996
72
999999885
12

【样例解释】

第一个询问：

$6 \times 1 \times 6=36$

第二个询问：

询问前各个球的权值为：$-6 2 3 -5 -3 -8 -3 7 2 6$

$2+3+(-5)+(-3)+(-8)=-11$

$-11+(10^9+7)=999999996$

第三个询问：

询问前各个球的权值为：$-6 2 3 -5 3 8 3 7 2 6$

$3 \times 8 \times 3=72$

Hint

对于 $100\%$ 的数据，$1 \le n,m \le 50000$，所有输入数据的绝对值均不超过 $10^9$，且$k \le b-a+1$。

每个测试点的规模及特点如下表：