动态开点的做法，官网满分，acwing这里最后两组数据会被卡常

#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N = 5760010, MAXN = 1000000000;
LL MOD = 1000000007ll;

struct Node {
    int ls, rs;
    int s[3];
    int mul[3][3], add[3];
}tr[N];

int rt[3][3] = {
    {0, 0, 1},
    {1, 0, 0},
    {0, 1, 0},
};

int m1[3][3] = {
    {1, 0, 0},
    {0, 1, 0},
    {0, 0, 1},
};

int root, idx;
int n, m;

struct R {
    int c[3];
};

bool check_one(int a[][3])
{
    for (int i = 0; i < 3; ++i)
        for (int j = 0; j < 3; ++j)
            if (a[i][j] != m1[i][j]) return false;
    return true;
}

bool check_zero(int a[])
{
    for (int i = 0; i < 3; ++i)
        if (a[i]) return false;
    return true;
}

void set_one(int a[][3])
{
    for (int i = 0; i < 3; ++i)
        for (int j = 0; j < 3; ++j)
            if (i == j) a[i][j] = 1;
            else a[i][j] = 0;
}

void set_zero(int t[])
{
    for (int i = 0; i < 3; ++i) t[i] = 0;
}

void init(int u)
{
    set_one(tr[u].mul);
}

void addvec(int c[], int a[], int b[])
{
    static int res[3];
    memset(res, 0, sizeof res);
    for (int i = 0; i < 3; ++i) res[i] = ((LL)a[i] + b[i]) % MOD;
    memcpy(c, res, sizeof res);
}

void mulmat(int c[][3], int a[][3], int b[][3])
{
    static int res[3][3];
    memset(res, 0, sizeof res);
    for (int i = 0; i < 3; ++i)
        for (int j = 0; j < 3; ++j)
            for (int k = 0; k < 3; ++k)
                res[i][j] = (res[i][j] + (LL)a[i][k] * b[k][j]) % MOD;
    memcpy(c, res, sizeof res);
}

void mulvec(int c[], int a[], int b[][3])
{
    static int res[3];
    memset(res, 0, sizeof res);
    for (int i = 0; i < 3; ++i)
        for (int j = 0; j < 3; ++j)
            res[i] = (res[i] + ((LL)a[j] * b[j][i]) % MOD) % MOD;
    memcpy(c, res, sizeof res);
}

void mulmatv(int c[][3], int a[][3], int v)
{
    static int res[3][3];
    memset(res, 0, sizeof res);
    for (int i = 0; i < 3; ++i)
        for (int j = 0; j < 3; ++j)
            res[i][j] = ((LL)a[i][j] * v) % MOD;
    memcpy(c, res, sizeof res);
}

void mulvecv(int c[], int a[], int v)
{
    static int res[3];
    memset(res, 0, sizeof res);
    for (int i = 0; i < 3; ++i) res[i] = ((LL)a[i] * v) % MOD;
    memcpy(c, res, sizeof res);
}

void pushup(int u)
{
    addvec(tr[u].s, tr[tr[u].ls].s, tr[tr[u].rs].s);
}

void pushdown(int u, int ul, int ur)
{
    if (!tr[u].ls) tr[u].ls = ++idx, init(tr[u].ls);
    if (!tr[u].rs) tr[u].rs = ++idx, init(tr[u].rs);
    auto& lc = tr[tr[u].ls], & rc = tr[tr[u].rs];
    if (!check_one(tr[u].mul))
    {
        mulmat(lc.mul, lc.mul, tr[u].mul);
        mulvec(lc.add, lc.add, tr[u].mul);
        mulvec(lc.s, lc.s, tr[u].mul);
        mulmat(rc.mul, rc.mul, tr[u].mul);
        mulvec(rc.add, rc.add, tr[u].mul);
        mulvec(rc.s, rc.s, tr[u].mul);
        set_one(tr[u].mul);
    }
    if (!check_zero(tr[u].add))
    {
        addvec(lc.add, lc.add, tr[u].add);
        addvec(rc.add, rc.add, tr[u].add);
        int t1[3], t2[3];
        memcpy(t1, tr[u].add, sizeof t1);
        memcpy(t2, tr[u].add, sizeof t2);
        int mid = (ul + ur) / 2;
        mulvecv(t1, t1, mid - ul + 1);
        mulvecv(t2, t2, ur - mid);
        addvec(lc.s, lc.s, t1);
        addvec(rc.s, rc.s, t2);
        set_zero(tr[u].add);
    }
}

void modify_add(int u, int ul, int ur, int l, int r, int t[])
{
    if (ul >= l && ur <= r)
    {
        int tmp[3] = {};
        memcpy(tmp, t, sizeof(tmp));
        addvec(tr[u].add, tr[u].add, tmp);
        mulvecv(tmp, tmp, ur - ul + 1);
        addvec(tr[u].s, tr[u].s, tmp);
        return;
    }
    pushdown(u, ul, ur);
    int mid = (ul + ur) / 2;
    if (l <= mid)
    {
        modify_add(tr[u].ls, ul, mid, l, r, t);
    }
    if (r > mid)
    {
        modify_add(tr[u].rs, mid + 1, ur, l, r, t);
    }
    pushup(u);
}

void modify_mv(int u, int ul, int ur, int l, int r, int v)
{
    if (ul >= l && ur <= r)
    {
        mulmatv(tr[u].mul, tr[u].mul, v);
        mulvecv(tr[u].add, tr[u].add, v);
        mulvecv(tr[u].s, tr[u].s, v);
        return;
    }
    pushdown(u, ul, ur);
    int mid = (ul + ur) / 2;
    if (l <= mid)
    {
        modify_mv(tr[u].ls, ul, mid, l, r, v);
    }
    if (r > mid)
    {
        modify_mv(tr[u].rs, mid + 1, ur, l, r, v);
    }
    pushup(u);
}

void modify_mm(int u, int ul, int ur, int l, int r, int t[][3])
{
    if (ul >= l && ur <= r)
    {
        mulmat(tr[u].mul, tr[u].mul, t);
        mulvec(tr[u].add, tr[u].add, t);
        mulvec(tr[u].s, tr[u].s, t);
        return;
    }
    pushdown(u, ul, ur);
    int mid = (ul + ur) / 2;
    if (l <= mid)
    {
        modify_mm(tr[u].ls, ul, mid, l, r, t);
    }
    if (r > mid)
    {
        modify_mm(tr[u].rs, mid + 1, ur, l, r, t);
    }
    pushup(u);
}

R query(int u, int ul, int ur, int l, int r)
{
    if (ul >= l && ur <= r)
    {
        R res = {};
        memcpy(res.c, tr[u].s, sizeof(res.c));
        return res;
    }
    pushdown(u, ul, ur);
    int mid = (ul + ur) / 2;
    R res = {};
    memset(res.c, 0, sizeof res.c);
    if (l <= mid)
    {
        R rl = query(tr[u].ls, ul, mid, l, r);
        addvec(res.c, res.c, rl.c);
    }
    if (r > mid)
    {
        R rr = query(tr[u].rs, mid + 1, ur, l, r);
        addvec(res.c, res.c, rr.c);
    }
    return res;
}

int main()
{
    scanf("%d%d", &n, &m);
    root = ++idx;
    init(root);
    while (m--)
    {
        int op, l, r, a, b, c, k;
        scanf("%d%d%d", &op, &l, &r);
        if (op == 1)
        {
            scanf("%d%d%d", &a, &b, &c);
            int t[3] = { a, b, c };
            modify_add(root, 1, MAXN, l, r, t);
        }
        else if (op == 2)
        {
            scanf("%d", &k);
            modify_mv(root, 1, MAXN, l, r, k);
        }
        else if (op == 3)
        {
            modify_mm(root, 1, MAXN, l, r, rt);
        }
        else if (op == 4)
        {
            R res = query(root, 1, MAXN, l, r);
            LL ans = 0ll;
            for (int i = 0; i < 3; ++i)
                ans = ans + (LL)res.c[i] * res.c[i];
            printf("%lld\n", ans % MOD);
        }
    }

    return 0;
}