void pushdown(int root,int l,int r) {
	//下沉乘法懒标记 
	if(tr[root].tag1 != 1) {
		tr[root << 1].tag1 *= tr[root].tag1;
		tr[root << 1 | 1].tag1 *= tr[root].tag1;
		tr[root << 1].sum *= tr[root].tag1;
		tr[root << 1 | 1].sum *= tr[root].tag1;
		tr[root << 1].sum %= mod;
		tr[root << 1 | 1].sum %= mod;
		tr[root].tag1 = 1;
	}
	//下沉加法懒标记
	if(tr[root].tag2 > 0) {
		int mid = (l + r) >> 1;
		tr[root << 1].tag2 += tr[root].tag2;
		tr[root << 1 | 1].tag2 += tr[root].tag2;
		tr[root << 1].sum += (tr[root].tag2 * (mid - l + 1));
		tr[root << 1].sum %= mod;
		tr[root << 1].sum += (tr[root].tag2 * (r - mid));
		tr[root << 1].sum %= mod;
		tr[root].tag2 = 0;
	}
}

void update1(int root,int l,int r,int ql,int qr,int val) {
	if(ql <= l && qr >= r) {
		tr[root].tag1 *= val;
		tr[root].sum *= val;
		tr[root].sum %= mod;
		return;
	}
	pushdown(root,l,r);
	int mid = (l + r) >> 1;
	if(l <= mid) update1(root << 1,l,mid,ql,qr,val);
	if(r > mid) update1(root << 1 | 1,mid + 1,r,ql,qr,val);
	tr[root].sum = tr[root << 1].sum + tr[root << 1 | 1].sum;
	tr[root].sum %= mod;
	return;
}

void update2(int root,int l,int r,int ql,int qr,int val) {
	if(ql <= l && qr >= r) {
		tr[root].tag2 += val;
		tr[root].sum += (val * (r - l + 1));
		tr[root].sum %= mod;
		return;
	}
	pushdown(root,l,r);
	int mid = (l + r) >> 1;
	if(l <= mid) update2(root << 1,l,mid,ql,qr,val);
	if(r > mid) update2(root << 1 | 1,mid + 1,r,ql,qr,val);
	tr[root].sum = tr[root << 1].sum + tr[root << 1 | 1].sum;
	tr[root].sum %= mod;
	return;
}