#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 MOD = 1e9 + 7; //↓遅延セグ木ここから //↓変える typedef struct sayouso { ll p, q, r; }sayouso; typedef struct atai { ll a, f; }atai; //↑変える typedef struct node { sayouso T; atai x; }node; vectorlsegN; ll lsegNUM, lsegk; //↓変える sayouso id = { 1,0,0 }; atai xx(atai x, atai y) { atai ret; ret.a = (x.a + y.a) % MOD; ret.f = (x.f + y.f) % MOD; return ret; } atai Tx(sayouso T, atai x) { atai ret; ret.a = (T.p*x.a + T.q*x.f + T.r)%MOD; ret.f = x.f; return ret; } sayouso TT(sayouso S, sayouso T) { sayouso ret; ret.p = S.p*T.p%MOD; ret.q = (S.p*T.q + S.q) % MOD; ret.r = (S.p*T.r + S.r) % MOD; return ret; } sayouso fT(sayouso T, ll k) { sayouso ret; ret.p = T.p; ret.q = T.q; ret.r = (T.r << k) % MOD; return ret; } //↑ここまで変える void lseguse(ll n) { lsegNUM = 1; lsegk = 1; while (lsegNUM < n) { lsegNUM *= 2LL; lsegk++; } lsegN.resize(2 * lsegNUM); } void lseginit(){ for (ll i = lsegNUM - 1; i > 0; i--)lsegN[i].x = xx(lsegN[2 * i].x,lsegN[2*i+1].x); for (int i = 0; i < 2LL * lsegNUM; i++)lsegN[i].T = id; } void _update(ll l, ll r, sayouso T, ll i, ll cl, ll cr,ll ck) { //区間が含まれていないときは何もしない 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; _update(l,r,T,2*i,cl,cm,ck-1); _update(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 update(ll l, ll r, sayouso T) { _update(l,r,T,1,0,lsegNUM,lsegk); } atai _calc(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 _calc(l,r,2*i,cl,cm,ck-1); if (cm <= l)return _calc(l,r,2*i+1,cm,cr,ck-1); return xx(_calc(l, r, 2 * i, cl, cm, ck - 1), _calc(l, r, 2 * i + 1, cm, cr, ck - 1)); } atai calc(ll l, ll r) { return _calc(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(calc(l, r + 1).a*k%MOD); else if (q == 1) { T.p = 0; T.q = 0; T.r = k; update(l,r+1,T); } else if (q == 2) { T.p = 1; T.q = 0; T.r = k; update(l, r + 1, T); } else if (q == 3) { T.p = k; T.q = 0; T.r = 0; update(l, r + 1, T); } else if (q == 4) { T.p = 1; T.q = k; T.r = 0; update(l, r + 1, T); } } return 0; }