关于HDU oj

#include<iostream>
using namespace std;
using ll=long long;
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
const ll mod=10007;
struct node{
	ll s[10],add,mul;
}t[400005];
ll n,m,a[100005];
void push_up(ll p){
	t[p].s[1]=(t[ls(p)].s[1]+t[rs(p)].s[1])%mod;
	t[p].s[2]=(t[ls(p)].s[2]+t[rs(p)].s[2])%mod;
	t[p].s[3]=(t[ls(p)].s[3]+t[rs(p)].s[3])%mod;
}
void build(ll p,ll l,ll r){
	t[p].mul=1,t[p].add=0;
	if(l==r){
		t[p].s[1]=a[l];
		t[p].s[2]=a[l]*a[l];
		t[p].s[3]=a[l]*a[l]*a[l];
	}
	else{
		ll m=l+r>>1;
		build(ls(p),l,m);
		build(rs(p),m+1,r);
		push_up(p);
	}
}
void push_down(ll p,ll l,ll r){
	if(!t[p].add&&t[p].mul==1) return;
	t[p].add%=mod,t[p].mul%=mod;
	ll m=(l+r)>>1;
	ll lenl=m-l+1,lenr=r-(m+1)+1;
	t[ls(p)].s[3]=(t[ls(p)].s[3]*t[p].mul+3*t[p].add*t[ls(p)].s[2]+3*t[p].add*t[p].add*t[ls(p)].s[1]+lenl*t[p].add*t[p].add*t[p].add)%mod;
	t[rs(p)].s[3]=(t[rs(p)].s[3]*t[p].mul+3*t[p].add*t[rs(p)].s[2]+3*t[p].add*t[p].add*t[rs(p)].s[1]+lenr*t[p].add*t[p].add*t[p].add)%mod;
	t[ls(p)].s[2]=(t[ls(p)].s[2]*t[p].mul+2*t[p].add*t[ls(p)].s[1]+lenl*t[p].add*t[p].add)%mod;
	t[rs(p)].s[2]=(t[rs(p)].s[2]*t[p].mul+2*t[p].add*t[rs(p)].s[1]+lenr*t[p].add*t[p].add)%mod;	
	t[ls(p)].s[1]=(t[ls(p)].s[1]*t[p].mul+t[p].add*lenl)%mod;
	t[rs(p)].s[1]=(t[rs(p)].s[1]*t[p].mul+t[p].add*lenr)%mod;
	t[ls(p)].mul=(t[ls(p)].mul*t[p].mul)%mod;
	t[ls(p)].add=(t[ls(p)].add*t[p].mul+t[p].add)%mod;
	t[rs(p)].mul=(t[rs(p)].mul*t[p].mul)%mod;
	t[rs(p)].add=(t[rs(p)].add*t[p].mul+t[p].add)%mod;	
	t[p].add=0,t[p].mul=1;
}
void update_add(ll p,ll tl,ll tr,ll l,ll r,ll k){
	if(tl<=l&&r<=tr){
		ll len=r-l+1;
		t[p].s[3]=(t[p].s[3]+3*k*t[p].s[2]+3*k*k*t[p].s[1]+len*k*k*k)%mod;
		t[p].s[2]=(t[p].s[2]+2*k*t[p].s[1]+len*k*k)%mod;
		t[p].s[1]=(t[p].s[1]+k*len)%mod;
		t[p].add=(t[p].add+k)%mod;
	}
	else{
		ll m=(l+r)>>1;
		push_down(p,l,r);
		if(tl<=m) update_add(ls(p),tl,tr,l,m,k);
		if(m+1<=tr) update_add(rs(p),tl,tr,m+1,r,k);
		push_up(p);
	}
}
void update_mul(ll p,ll tl,ll tr,ll l,ll r,ll k){
	if(tl<=l&&r<=tr){
		t[p].s[1]=(t[p].s[1]*k)%mod;
		t[p].s[2]=(t[p].s[2]*k*k)%mod;
		t[p].s[3]=(t[p].s[3]*k*k*k)%mod;
		t[p].mul=(t[p].mul*k)%mod;
		t[p].add=(t[p].add*k)%mod;
	}
	else{
		ll m=(l+r)>>1;
		push_down(p,l,r);
		if(tl<=m) update_mul(ls(p),tl,tr,l,m,k);
		if(m+1<=tr) update_mul(rs(p),tl,tr,m+1,r,k);
		push_up(p);
	}
}
ll query(ll p,ll tl,ll tr,ll l,ll r,ll pw){
	if(tl<=l&&r<=tr) return t[p].s[pw]%mod;
	ll res=0,m=(l+r)>>1;
	push_down(p,l,r);
	if(tl<=m) res+=query(ls(p),tl,tr,l,m,pw);
	if(m+1<=tr) res+=query(rs(p),tl,tr,m+1,r,pw);
	return res%mod;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	while(cin>>n>>m){
		if(!n&&!m) break;
		build(1,1,n);
		while(m--){
			int op,x,y,z;
			cin>>op>>x>>y>>z;
			z%=mod;
			if(op==1) update_add(1,x,y,1,n,z);
			else if(op==2) update_mul(1,x,y,1,n,z);
			else if(op==3) update_mul(1,x,y,1,n,0),update_add(1,x,y,1,n,z);
			else cout<<query(1,x,y,1,n,z)<<'\n';
		}
	}
	return 0;
}