维护具有下列两个操作的序列A。
1.：1 l r x 修改A[i]+=x(l<=i<=r)；
2.：2 l r 输出$\Sigma_{i=l}^rf(A[i])\%1000000007$，其中f(i)表示斐波拉契数列的第i项。
输入格式：
第一行两个数n,m分别表示序列长度和操作数。
第二行n个数表示序列初始的值。
接下来m行表示每个操作。
数据范围
30% n,m<=1000
100% $n,m<=100000,1<=A[i],x<=10^9$。
Sample Input

5 4
1 1 2 1 1
2 1 5
1 2 4 2
2 2 4
2 1 5

5
7
9