分析：矩阵快速幂+线段树 斐波那契数列的计算是矩阵快速幂的模板题，这个也没什么很多好解释的，学了矩阵快速幂应该就知道的东西= =这道题比较巧妙的在于需要用线段树来维护矩阵，达到快速查询区间斐波那契数列和的目的。这道题极为卡常数，我TLE了不知道多少发，才在赛后过了这道题。
我尝试下来，发现矩阵乘法的写法极为重要，我就是因为用了三层循环来写矩阵乘法导致了悲剧的TLE，一直卡在了第17组数据。我百度了网上别的矩阵快速幂的写法才过了这道题。
还有涨智识的地方是不要随意memset。我原来的矩阵快速幂的模板里面在构造函数的时候会memset元素为0，去掉了这句话，代码快了1s。。。
毕竟萌新还是太嫩，没有很多老司机的经验。。貌似bc87场的第三题也是卡了memset的常数。我也TLE了一发。
/*****************************************************/
// #pragma comment(linker, "/STACK:1024000000,1024000000")
#include <map>
#include <set>
#include <ctime>
#include <stack>
#include <queue>
#include <cmath>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <sstream>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
#define offcin ios::sync_with_stdio(false)
#define sigma_size 26
#define lson l,m,v<<1
#define rson m+1,r,v<<1|1
#define slch v<<1
#define srch v<<1|1
#define sgetmid int m = (l+r)>>1
#define LL long long
#define ull unsigned long long
#define mem(x,v) memset(x,v,sizeof(x))
#define lowbit(x) (x&-x)
#define bits(a) __builtin_popcount(a)
#define mk make_pair
#define pb push_back
#define fi first
#define se second
const int INF = 0x3f3f3f3f;
const LL INFF = 1e18;
const double pi = acos(-1.0);
const double inf = 1e18;
const double eps = 1e-9;
const LL mod = 1e9+7;
const int maxmat = 10;
const ull BASE = 31;
/*****************************************************/
const int maxn = 1e5 + 5;
int a[maxn];
int N, M;
struct Mat {
int N;
LL a[2][2];
Mat (int _n = 2) : N(_n) {
//这里我原来会memset
}
void Debug() {
for (int i = 0; i < N; i ++) {
for (int j = 0; j < N; j ++)
cout<<a[i][j]<<" ";
cout<<endl;
}
}
// Mat operator *(const Mat &rhs) const { //悲剧的三重循环写法
// Mat c(N);
// for (int i = 0; i < N; i ++)
// for (int k = 0; k < N; k ++) {
// if (!a[i][k]) continue;
// for (int j = 0; j < N; j ++)
// c.a[i][j] = (c.a[i][j] + a[i][k] * rhs.a[k][j] % mod) % mod;
// }
// return c;
// }
Mat operator *(const Mat &rhs) const { //同时也能能够避免三重循环需要先memset矩阵的时间复杂度
Mat ret;
ret.a[0][0] = (1ll * a[0][0] * rhs.a[0][0] + 1ll * a[0][1] * rhs.a[1][0]) % mod;
ret.a[1][0] = ret.a[0][1] = (1ll * a[0][0] * rhs.a[0][1] + 1ll * a[0][1] * rhs.a[1][1]) % mod;
ret.a[1][1] = (1ll * a[1][0] * rhs.a[0][1] + 1ll * a[1][1] * rhs.a[1][1]) % mod;
return ret;
}
Mat operator +(const Mat &rhs) const {
Mat c(N);
for (int i = 0; i < N; i ++)
for (int j = 0; j < N; j ++)
c.a[i][j] = (a[i][j] + rhs.a[i][j]) % mod;
return c;
}
};
Mat E(2), F(2);
void init() {
E.a[0][0] = E.a[1][1] = 1;
F.a[0][0] = F.a[0][1] = F.a[1][0] = 1;
}
Mat qpow(Mat A, LL b) {
Mat c = E;
while (b > 0) {
if (b & 1) c = A * c;
b >>= 1;
A = A * A;
}
return c;
}
Mat seg[maxn << 2], col[maxn << 2];
bool add[maxn << 2];
void PushUp(int v) {
seg[v] = seg[slch] + seg[srch];
}
void PushDown(int v, int m) {
if (!add[v]) return;
col[slch] = col[slch] * col[v];
col[srch] = col[srch] * col[v];
seg[slch] = seg[slch] * col[v];
seg[srch] = seg[srch] * col[v];
add[slch] = add[srch] = true;
col[v] = E;
add[v] = false;
}
void build(int l, int r, int v) {
col[v] = E;
if (l == r) {
int k;
scanf("%d", &k);
seg[v] = qpow(F, k - 1);
}
else {
sgetmid;
build(lson);
build(rson);
PushUp(v);
}
}
void update(int L, int R, int x, int l, int r, int v) {
if (L <= l && r <= R) {
Mat temp = qpow(F, x);
seg[v] = seg[v] * temp;
col[v] = col[v] * temp;
add[v] = true;
return;
}
sgetmid;
PushDown(v, r - l + 1);
if (L <= m) update(L, R, x, lson);
if (R > m) update(L, R, x, rson);
PushUp(v);
}
LL query(int L, int R, int l, int r, int v) {
if (L <= l && r <= R) return seg[v].a[0][0];
sgetmid;
PushDown(v, r - l + 1);
LL ans = 0;
if (L <= m) ans = (ans + query(L, R, lson)) % mod;
if (R > m) ans = (ans + query(L, R, rson)) % mod;
return ans;
}
int main(int argc, char const *argv[]) {
cin>>N>>M; init(); mem(add, false);
build(1, N, 1);
while (M --) {
int op;
scanf("%d", &op);
if (op == 1) {
int l, r, x;
scanf("%d%d%d", &l, &r, &x);
update(l, r, x, 1, N, 1);
}
else {
int l, r;
scanf("%d%d", &l, &r);
printf("%I64d\n", query(l, r, 1, N, 1));
}
}
return 0;
}