#include #define mod 1000000007 using namespace std; struct matr{ int a12,a13,a14; int a22,a23,a24; int a33,a34; }li,sm[400005],ss[100005]; inline matr operator*(matr a,matr b){ matr c=li; c.a12=(b.a12+1ll*a.a12*b.a22)%mod; c.a13=(b.a13+1ll*a.a12*b.a23+1ll*a.a13*b.a33)%mod; c.a14=(a.a14+b.a14+1ll*a.a13*b.a34+1ll*a.a12*b.a24)%mod; c.a22=(1ll*a.a22*b.a22)%mod; c.a23=(1ll*a.a22*b.a23+1ll*a.a23*b.a33)%mod; c.a24=(a.a24+1ll*a.a22*b.a24+1ll*a.a23*b.a34)%mod; c.a33=(1ll*a.a33*b.a33)%mod; c.a34=(a.a34+1ll*a.a33*b.a34)%mod; return c; } void build(int l,int r,int o){ sm[o].a12=sm[o].a13=1; if(l==r){ ss[l]=sm[o]; return; } int mid=(l+r)>>1; build(l,mid,o<<1);build(mid+1,r,o<<1|1); } void add(int l,int r,int o,int x){ if(l==r){ sm[o]=ss[x]; return; } int mid=(l+r)>>1; if(x<=mid)add(l,mid,o<<1,x); else add(mid+1,r,o<<1|1,x); sm[o]=sm[o<<1]*sm[o<<1|1]; } int a2,a3,a4; int b2,b3,b4; void query(int l,int r,int o,int ll,int rr){ if(l>=ll&&r<=rr){ b2=(1ll*a2*sm[o].a22+sm[o].a12)%mod; b3=(1ll*a2*sm[o].a23+1ll*a3*sm[o].a33+sm[o].a13)%mod; b4=(1ll*a2*sm[o].a24+1ll*a3*sm[o].a34+a4+sm[o].a14)%mod; a2=b2,a3=b3,a4=b4; return; } int mid=(l+r)>>1; if(mid>=ll)query(l,mid,o<<1,ll,rr); if(mid