#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; templateusing min_priority_queue = priority_queue, greater>; const ll inf = 1LL << 60; #define all(x) (x).begin(),(x).end() #define puts(x) cout << x << endl #define rep(i,m,n) for(ll i = m;i < n;++i) #define pb push_back #define fore(i,a) for(auto &i:a) #define rrep(i,m,n) for(ll i = m;i >= n;--i) ll M = 1e9 + 7; ll MOD = M; //遅延セグ木ここから //↓ここを変える typedef struct sayouso { ll p, q, r; }sayouso; typedef struct atai { ll a, f; }atai; //↑ここを変える typedef struct node { sayouso T; atai x; }node; node lsegN[1 << 21], *lseg; ll lsegNUM, lsegk; //↓ここから変える sayouso id = { 1,0,0 }; atai xx(atai x, atai y) { atai ret; ret.a = (x.a + y.a) % M; ret.f = (x.f + y.f) % M; return ret; } atai Tx(sayouso T, atai x) { atai ret; ret.a = (T.p*x.a + T.q*x.f + T.r) % M; ret.f = x.f; return ret; } sayouso TT(sayouso S, sayouso T) { sayouso ret; ret.p = S.p*T.p%M; ret.q = (S.p*T.q + S.q) % M; ret.r = (S.p*T.r + S.r) % M; return ret; } sayouso fT(sayouso T, ll k) { sayouso ret; ret.p = T.p; ret.q = T.q; ret.r = (T.r << k) % M; return ret; } //↑ここまで変える void lseguse(ll n) { lsegNUM = n; lseg = lsegN + lsegNUM; lsegk = 0; while (n /= 2)lsegk++; } void lseginit() { for (ll i = lsegNUM - 1; i>0; i--)lsegN[i].x = xx(lsegN[2 * i].x, lsegN[2 * i + 1].x); rep(i, 1, 2 * lsegNUM)lsegN[i].T = id; } void lsegupdatesub(ll l, ll r, sayouso T, ll i, ll cl, ll cr, ll ck) { //disjointなとき if (cr <= l || r <= cl)return; //完全に含むとき if (l <= cl && cr <= r) { lsegN[i].T = TT(T, lsegN[i].T); return; } //どちらでもないとき //遅延伝播 lsegN[2 * i].T = TT(lsegN[i].T, lsegN[2 * i].T); lsegN[2 * i + 1].T = TT(lsegN[i].T, lsegN[2 * i + 1].T); //再帰的に更新 ll cm = (cl + cr) / 2; lsegupdatesub(l, r, T, 2 * i, cl, cm, ck - 1); lsegupdatesub(l, r, T, 2 * i + 1, cm, cr, ck - 1); //自身のnodeを更新 lsegN[i].x = xx(Tx(fT(lsegN[2 * i].T, ck - 1), lsegN[2 * i].x), Tx(fT(lsegN[2 * i + 1].T, ck - 1), lsegN[2 * i + 1].x)); lsegN[i].T = id; } void lsegupdate(ll l, ll r, sayouso T) { lsegupdatesub(l, r, T, 1, 0, lsegNUM, lsegk); } atai lsegcalcsub(ll l, ll r, ll i, ll cl, ll cr, ll ck) { //完全に含むとき if (l <= cl && cr <= r)return Tx(fT(lsegN[i].T, ck), lsegN[i].x); ll cm = (cl + cr) / 2; //遅延伝播(変更はないので配るだけで良い) lsegN[2 * i].T = TT(lsegN[i].T, lsegN[2 * i].T); lsegN[2 * i + 1].T = TT(lsegN[i].T, lsegN[2 * i + 1].T); lsegN[i].x = Tx(fT(lsegN[i].T, ck), lsegN[i].x); lsegN[i].T = id; //左側だけ if (r <= cm)return lsegcalcsub(l, r, 2 * i, cl, cm, ck - 1); //右側だけ if (cm <= l)return lsegcalcsub(l, r, 2 * i + 1, cm, cr, ck - 1); //両方 return xx(lsegcalcsub(l, r, 2 * i, cl, cm, ck - 1), lsegcalcsub(l, r, 2 * i + 1, cm, cr, ck - 1)); } atai lsegcalc(ll l, ll r) { return lsegcalcsub(l, r, 1, 0, lsegNUM, lsegk); } //遅延セグ木ここまで int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int Q; cin >> Q; lseguse(1 << 20); lsegN[1].x.f = 1; for (int i = 2; i < 1000100; i++)lsegN[i].x.f = (lsegN[i - 1].x.f + lsegN[i-2].x.f) % MOD; lseginit(); for (int i = 0; i < Q; i++) { ll q, l, r, k; sayouso T; cin >> q >> l >> r >> k; if (q == 0)puts(lsegcalc(l, r + 1).a*k%MOD); else if (q == 1) { T.p = 0; T.q = 0; T.r = k; lsegupdate(l,r+1,T); } else if (q == 2) { T.p = 1; T.q = 0; T.r = k; lsegupdate(l, r + 1, T); } else if (q == 3) { T.p = k; T.q = 0; T.r = 0; lsegupdate(l, r + 1, T); } else if (q == 4) { T.p = 1; T.q = k; T.r = 0; lsegupdate(l, r + 1, T); } } return 0; }