测试数据来自 system/1958

描述

万老板希望在新的智能音乐播放设备IPOOD中，实现对波文件音质性能的评定。

离散的波文件被考虑为长度为N的整数序列：$A_1,A_2,\cdots,A_N$。所谓的音质性能检测，可以评定任何的一个区间范围$[L,R]$，其音质性能取决于下述评分：

$\Big\{ \sum_{L<i<R} F[A_{i-1}+1]F[A_{i+1}-1] \Big\} \mod (10^9+7)$

其中F是可归纳定义的数列，满足$F[1]=1$，$F[2]=2$且$F[k+2]=F[k+1]+aF[k]+b$对于任何$k\ge 1$成立。其中a 和b为正整系数。

为了可以为用户提供更好的服务体验，并希望对给定的波文件进行修正优化。这一款设备中，还应该支持对波文件的修改。
对于给定的区间范围$[L,R]$，允许用户将$A[L]$至$A[R]$同时增加一，或同时减少一。

格式

输入格式

输入的第一行有两个正整数，波文件的总长度$N$，和总的修改与询问次数$Q$。

第二行有两个整数，分别表示系数$a$和$b$。

之后若干行，一共给出$N$个正整数$A_1$到$A_N$，满足$1 \le A[i] \le 2*10^9$。

之后$Q$行，每行是下述三种形式之一：

$plus~L~R$：将波文件数列中下标在区间$[L,R]$内的元素每一个都加一。

$minus~L~R$：将波文件数列中下标在区间$[L,R]$内的元素每一个都减一。

$query~L~R$：询问区间$[L,R]$的音质性能评分。

修改和询问中，均保证$L\le R$，且保证$A[i]$严格大于总的修改次数加一（修改操作包括plus和minus两种）。

输出格式

输出若干行，每一行对应一次询问，输出一个整数。

样例1

样例输入1

7 7
1 0
3 4 5 6 7 8 9
query 2 4
query 3 7
plus 3 5
query 2 4
plus 4 7
query 3 7
query 1 7

样例输出1

64
1766
104
7479
7687

样例2

样例输入2

7 12
123456789 987654321
1111111111 1222222222 1333333333
1444444444 1555555555 1666666666 1777777777
query 2 4
query 3 7
plus 3 5
minus 4 6
plus 5 7
query 2 4
query 1 6
plus 4 7
minus 1 4
query 3 7
query 2 6
query 1 7

样例输出2

528103209
239947280
528103209
229970829
524160263
336413855
113033289

限制

对于15%的数据，$N\le 8000，Q\le 8000$。

对于100%的数据，$N\le 100000，Q\le 100000，0\le a,b\le 10^9$。

此外：

存在15%的数据，每一次修改的区间都是[1,N]。

还存在30%的数据，a=0，b=1。

来源

SDOI 2015 round2 day1