Untitled

typedef ll item;

int powerOf2[N];

ll mul(int a, int b){
    return (a + b) % MOD;
}


struct segTree {
    int size = 1;
    vector<item> modifyOperation;
    vector<item> getOperation;
    item NEUTRAL_ELEMENT = 0;

//    item modify_1(item a, item b) {
//        return a ^ b;
//    }

    item modify_2(item a, item b) {
        return (a + b) % MOD;
    }

//    item applyOperation(item &a, item b) {
//        a = modify_1(a, b);
//    }

    void init(int n) {
        while (size < n) size <<= 1;
        modifyOperation.resize(2 * size);
        getOperation.resize(2 * size);
    }

    void build(vector<int> &ref, int x, int lx, int rx) {
        if (rx - lx == 1) {
            if (lx < ref.size())
                getOperation[x] = mul(ref[lx], powerOf2[lx]);
            return;
        }
        int m = (lx + rx) / 2;

        build(ref, 2 * x + 1, lx, m);
        build(ref, 2 * x + 2, m, rx);
        getOperation[x] = modify_2(getOperation[2 * x + 1], getOperation[2 * x + 2]);
    }


    void build(vector<int> &ref) {
        build(ref, 0, 0, size);
    }


    void set(int i, int v, int x, int lx, int rx){
        if(rx - lx == 1){
            getOperation[x] = mul(v, powerOf2[lx]);
            return;
        }
        int m = (lx + rx) / 2;
        if(i < m)
            set(i, v, 2 * x + 1, lx, m);
        else
            set(i, v, 2 * x + 2, m, rx);
        
        getOperation[x] = modify_2(getOperation[2 * x + 1], getOperation[2 * x + 2]);
    }


    void set(int i, int v){
        set(i, v, 0, 0, size);
    }


//    void update(int l, int r, int b, int x, int lx, int rx) {
//        if (lx >= r || rx >= l) return;
//        if (lx >= l && rx <= r) {
//            applyOperation(modifyOperation[x], b);
//            applyOperation(getOperation[x], b);
//            return;
//        }
//        int m = (lx + rx) / 2;
//
//        update(l, r, b, 2 * x + 1, lx, m);
//        update(l, r, b, 2 * x + 2, m, rx);
//
//        getOperation[x] = modify_1(modify_2(getOperation[2 * x + 1], getOperation[2 * x + 2]), modifyOperation[x]);
//
//    }
//
//    void update(int l, int r, int b) {
//        update(l, r, b, 0, 0, size);
//    }

    ll get(int l, int r, int x, int lx, int rx) {
        if (lx >= r || rx >= l) return NEUTRAL_ELEMENT;
        if (lx >= l && rx <= r) {
            return getOperation[x];
        }
        int m = (lx + rx) / 2;

        auto val1 = get(l, r, 2 * x + 1, lx, m);
        auto val2 = get(l, r, 2 * x + 2, m, rx);

        return modify_2(val1, val2);

    }

    ll get(int l, int r) {
        return get(l, r, 0, 0, size);
    }

};