aBlDru - Online C++0x Compiler & Debugging Tool

/**
 *    author:  orzvanh14
 *    created: 23.12.2022 10:08:02
 *    too lazy to update time
**/
// i wants to take ioi
//binhtinhtutinkhongcaycunhungmotkhikhongcontutinnualatuyetvong
#include <bits/stdc++.h>

using namespace std;

#define int long long
#define nn "\n"
#define pi pair<int, int>
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define eb emplace_back
#define pb push_back
#define TASK " "

#define ms(a, x) memset(a, x, sizeof(a))
#define all(a) a.begin(), a.end()
#define All(a, n) a + 1, a + 1 + n

#define LOG 19


const int INF = 1e18;
const int mod = 1e3+7;
const int N = 2e5  + 5;
const int maxN = 1e5 + 5;
int MOD = 998244353;
int bit[200000];
struct node{
	int kc, u, hk;
	bool operator<(const node& other) const {
        return kc > other.kc;
    }
};
struct edge{
	int u, v, w, id;
	friend bool operator < ( edge a, edge b){
		return a.w > b.w;
	}
};
int n,q;
int a[N];
int st[4 * N]; int lazy[4 * N];
int dp[N];
void nhap(){
    cin >> n >> q;
	// for(int i = 1;i <= n; i++){
		// cin >> a[i];
	// }
}
pi fast_doubling(int n){
	if (n == 0) return {0, 1};
	pi p = fast_doubling(n >> 1);
	int fk = p.fi;
    int fk1 = p.se;
    int f2k = (fk * ((2 * fk1 - fk + mod) % mod)) % mod;
    int f2k1 = (fk1 * fk1 % mod + fk * fk % mod) % mod;
    if(n % 2 == 0) return {f2k, f2k1};
    else return {f2k1, (f2k + f2k1) % mod};
}
void build(int id, int l, int r){
	if(l == r){
		st[id] = a[l];
	}
	else{
		int m = l + r >> 1;
		build(2 * id, l, m);
		build(2 * id + 1, m + 1, r);
		st[id] = st[2 * id] + st[2 * id + 1];
	}
}
void fix(int id, int l, int r){
	if(!lazy[id]) return;
	st[id] = (st[id] + lazy[id] * (r - l + 1)) % mod;

	if(l != r){
		lazy[2 * id] = (lazy[2 * id] + lazy[id]) % mod;
        lazy[2 * id + 1] = (lazy[2 * id + 1] + lazy[id]) % mod;
	}
	lazy[id] = 0;
}
void update(int id, int l, int r, int u, int v,int val){
	fix(id, l, r);
	if(l > v || r < u) return;
	if(l >= u && r <= v){
		lazy[id] = (lazy[id] + fast_doubling(val).fi) % mod;
		fix(id, l, r);
		return;
	}
	int m = l + r >> 1;
	update(2 * id, l, m, u, v, val);
	update(2 * id + 1, m + 1, r, u, v, val);
	st[id] = (st[2 * id] + st[2 * id + 1]) % mod;
}
int get(int id,int l,int r,int u,int v){
	fix(id, l , r);
	if(l > v || u > r) return 0;
	if(l >= u && r <= v){
		return st[id];
	}
	int m = l + r >> 1;
	int get1 = get(2 * id, l, m, u, v);
	int get2 = get(2 * id + 1, m + 1, r, u, v);
	return (get1 + get2) % mod;
}
void solve(){
	int ans = 0;
	// build(1, 1, n);
	while(q--){
		int op;
		cin >> op;
		if(op == 1){
			int l, r, k;
			cin >> l >> r >> k;
			update(1, 1, n, l, r, k);
		}
		else{
			int l, r;
			cin >> l >> r;
			cout << get(1, 1, n, l, r) << nn;
		}
	}
}
signed main() {
	// freopen("piggyback.in", "r", stdin);
	// freopen("piggyback.out", "w", stdout);
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
    nhap();
    solve();
	return (0 ^ 0);

}