Description：

Solution：

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<map>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 100010

typedef long long ll;

#define MOD 1000000007

struct matrix

{

	ll m[3][3];

	matrix(){memset(m,0,sizeof(m));m[1][1] = m[2][2] = 1;}

	void init(){memset(m,0,sizeof(m));m[1][1] = m[2][2] = 1;}

	friend matrix operator * (matrix a,matrix b)

	{

		matrix c;

		for(int i = 1;i <= 2;++i)

		{

			for(int j = 1;j <= 2;++j)

			{

				c.m[i][j] = 0;

				for(int k = 1;k <= 2;++k)

				{

					c.m[i][j] = (c.m[i][j] + a.m[i][k] * b.m[k][j] % MOD) % MOD;

				}

			}

		}

		return c;

	}

	friend matrix operator + (matrix a,matrix b)

	{

		for(int i = 1;i <= 2;++i)

		{

			for(int j = 1;j <= 2;++j)

			{

				a.m[i][j] = (a.m[i][j] + b.m[i][j]) % MOD;

			}

		}

		return a;

	}

};

map<int,matrix> p;

matrix get(int b)

{

	if(p.find(b) != p.end())return p[b];

	matrix res,a;

	res.init();

	a.m[1][2] = a.m[2][1] = a.m[1][1] = 1;

	a.m[2][2] = 0;

	while(b > 0)

	{

		if(b & 1)res = res * a;

		a = a * a;

		b = b >> 1;

	}

	return (p[b] = res);

}

int x[MAXN];

struct node

{

	int lc,rc;

	matrix k,tag;

}t[MAXN << 1];

int ptr = 0;

int newnode(){return ++ptr;}

int root;

#define mid ((l + r) >> 1)

void build(int &rt,int l,int r)

{

	rt = newnode();

	if(l == r)

	{

		t[rt].k = get(x[l]);

		return;

	}

	build(t[rt].lc,l,mid);

	build(t[rt].rc,mid + 1,r);

	t[rt].k = t[t[rt].lc].k + t[t[rt].rc].k;

	return;

}

void pushdown(int rt)

{

	t[t[rt].lc].tag = t[t[rt].lc].tag * t[rt].tag;

	t[t[rt].lc].k = t[t[rt].lc].k * t[rt].tag;

	t[t[rt].rc].tag = t[t[rt].rc].tag * t[rt].tag;

	t[t[rt].rc].k = t[t[rt].rc].k * t[rt].tag;

	t[rt].tag.init();

	return;

}

void add(int rt,int L,int R,matrix a,int l,int r)

{

	if(L <= l && r <= R)

	{

		t[rt].k = t[rt].k * a;

		t[rt].tag = t[rt].tag * a;

		return;

	}

	pushdown(rt);

	if(L <= mid)add(t[rt].lc,L,R,a,l,mid);

	if(R > mid)add(t[rt].rc,L,R,a,mid + 1,r);

	t[rt].k = t[t[rt].lc].k + t[t[rt].rc].k;

	return;

}

matrix query(int rt,int L,int R,int l,int r)

{

	if(L <= l && r <= R)

	{

		return t[rt].k;

	}

	pushdown(rt);

	matrix res;res.m[1][1] = res.m[1][2] = res.m[2][1] = res.m[2][2] = 0;

	if(L <= mid)res = res + query(t[rt].lc,L,R,l,mid);

	if(R > mid)res = res + query(t[rt].rc,L,R,mid + 1,r);

	return res;

}

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= n;++i)

	{

		scanf("%d",&x[i]);

	}

	build(root,1,n);

	int type,l,r,x;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d",&type);

		if(type == 1)

		{

			scanf("%d%d%d",&l,&r,&x);

			add(root,l,r,get(x),1,n);

		}

		else

		{

			scanf("%d%d",&l,&r);

			printf("%I64d\n",query(root,l,r,1,n).m[2][1]);

		}

	}

	return 0;

}