/*************************************** codeforces = topcoder = sahedsohel IIT,Jahangirnagar University(42) ****************************************/ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define ll long long int #define ull unsigned long long int #define inf INT_MAX #define linf LLONG_MAX #define sc(a) scanf("%d",&a) #define sc2(a,b) scanf("%d%d",&a,&b) #define sc3(a,b,c) scanf("%d%d%d",&a,&b,&c) #define sc4(a,b,c,d) scanf("%d%d%d%d",&a,&b,&c,&d) #define fl(c,i,n) for(i=c;i #define pll pair< ll , ll > #define pcs(a) printf("Case %d: ",a) #define dbg(x) cout<<#x<<" : "< inline T bigmod(T p,T e,T M){ll ret = 1;for(; e > 0; e >>= 1){if(e & 1) ret = (ret * p) % M;p = (p * p) % M;}return (T)ret;} template inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);} template inline T modinverse(T a,T M){return bigmod(a,M-2,M);} // M is prime} template inline T bpow(T p,T e){ll ret = 1;for(; e > 0; e >>= 1){if(e & 1) ret = (ret * p);p = (p * p);}return (T)ret;} int toInt(string s){int sm;stringstream ss(s);ss>>sm;return sm;} int toLlint(string s){long long int sm;stringstream ss(s);ss>>sm;return sm;} ///int month[]={-1,31,28,31,30,31,30,31,31,30,31,30,31}; //Not Leap Year ///int dx[]={1,0,-1,0};int dy[]={0,1,0,-1}; //4 Direction ///int dx[]={1,1,0,-1,-1,-1,0,1};int dy[]={0,1,1,1,0,-1,-1,-1};//8 direction ///int dx[]={2,1,-1,-2,-2,-1,1,2};int dy[]={1,2,2,1,-1,-2,-2,-1};//Knight Direction ///int dx[]={-1,-1,+0,+1,+1,+0};int dy[]={-1,+1,+2,+1,-1,-2}; //Hexagonal Direction const double eps=1e-4; /*****************************************************************/ /////////////////////// GET SET GO /////////////////////////// /*****************************************************************/ #define sqr(x) ((x)*(x)) #define dst(q1,q2) sqrt(sqr(q1.xx-q2.xx)+sqr(q1.yy-q2.yy)) int ts,kk=1; #define M 100005 #define MX 1000005 #define MD 1000000007LL #define mid ((s+e)>>1) #define lft ((i<<1)+1) #define rgt (lft+1) int n,m; ll tr[M*4]; ll x; void bld(int i,int s,int e) { if(s==e) { scanf("%lld",&tr[i]); return ; } bld(lft,s,mid); bld(rgt,mid+1,e); tr[i]=tr[lft]+bigmod(x,(ll)mid-s+1,MD)*tr[rgt]; if(tr[i]>=MD)tr[i]%=MD; } void updt(int i,int s,int e,int p) { if(s==e) { scanf("%lld",&tr[i]); return ; } if( p<=mid )updt(lft,s,mid,p); else updt(rgt,mid+1,e,p); tr[i]=tr[lft]+bigmod(x,(ll)mid-s+1,MD)*tr[rgt]; if(tr[i]>=MD)tr[i]%=MD; } ll qry(int i,int s,int e,int st,int ed) { if( st<=s&&e<=ed )return tr[i]; if( ed<=mid )return qry(lft,s,mid,st,ed); else if(mid