Consider a labeled monoid (T) acting on an information monoid (S), forming the algebraic structure ((T, \times, 1_T, S, +, 0_S, \circ)).

The information monoid ((S, +, 0_S)) satisfies:

• Closure: (\forall x, y \in S), (x + y \in S).
• Associativity: (\forall x, y, z \in S), ((x + y) + z = x + (y + z)).
• Idantity element: (\exists 0_S \in S) such that (\forall x \in S), (x + 0_S = 0_S + x = x).

The labeled monoid ((T, \times, 1_T)) satisfies:

• Closure: (\forall a, b \in T), (a \times b \in T).
• Associativity: (\forall a, b, c \in T), ((a \times b) \times c = a \times (b \times c)).
• Identity element: (\exists 1_T \in T) such that (\forall a \in T), (a \times 1_T = 1_T \times a = a).

The left action of (T) on (S) is a mapping:

[\circ: T \times S \rightarrow S]

Below is a framework for ((T, \times, 1_T, S, +, 0_S, \circ)). Note that passing raw arrays (const int a[]) can be replaced with shallow copies of vectors (const std::vector<int> &a) for convenience.

struct S {
    i64 sum, sz;
    S() {}
    S(i64 _sum, i64 _sz) : sum(_sum), sz(_sz) {}
    void init(int x, int a[]) {
        *this = S(a[x], 1);
    }
};

struct T {
    i64 mul, add;
    T() : mul(1), add(0) {}
    T(i64 _mul, i64 _add) : mul(_mul), add(_add) {}
} I;

S operator+(const S &l, const S &r) {
    return S{ (l.sum + r.sum) % MOD, l.sz + r.sz };
}

T operator*(const T &l, const T &r) {
    return T{ (l.mul * r.mul) % MOD, (l.add * r.mul + r.add) % MOD };
}

S operator>>(const T &t, const S &f) {
    return S{ ( (f.sum * t.mul) % MOD + (f.sz * t.add) % MOD ) % MOD, f.sz };
}

Below is a segment tree template that generally does not require modification. At initialiaztion, the array address is passed (default name a).

#define ls (id << 1)
#define rs (id << 1 | 1)

struct Node {
    S f;
    T t;
} seg[MAXN * 4];

void push_up(int id) {
    seg[id].f = seg[ls].f + seg[rs].f;
}

void push_down(int id) {
    auto apply = [](int child, const T &tag) {
        seg[child].f = tag >> seg[child].f;
        seg[child].t = seg[child].t * tag;
    };
    apply(ls, seg[id].t);
    apply(rs, seg[id].t);
    seg[id].t = I;
}

void build(int id, int l, int r) {
    if (l == r) {
        seg[id].f.init(l, a);
        return;
    }
    int mid = (l + r) >> 1;
    build(ls, l, mid);
    build(rs, mid + 1, r);
    push_up(id);
}

S query(int id, int l, int r, int ql, int qr) {
    if (l == ql && r == qr) {
        return seg[id].f;
    }
    push_down(id);
    int mid = (l + r) >> 1;
    if (qr <= mid)
        return query(ls, l, mid, ql, qr);
    else if (ql > mid)
        return query(rs, mid + 1, r, ql, qr);
    else
        return query(ls, l, mid, ql, mid) + query(rs, mid + 1, r, mid + 1, qr);
}

void update(int id, int l, int r, int ql, int qr, const T &tag) {
    if (l == ql && r == qr) {
        seg[id].f = tag >> seg[id].f;
        seg[id].t = seg[id].t * tag;
        return;
    }
    push_down(id);
    int mid = (l + r) >> 1;
    if (qr <= mid)
        update(ls, l, mid, ql, qr, tag);
    else if (ql > mid)
        update(rs, mid + 1, r, ql, qr, tag);
    else {
        update(ls, l, mid, ql, mid, tag);
        update(rs, mid + 1, r, mid + 1, qr, tag);
    }
    push_up(id);
}