long long s[maxn * 4];
long long lz[maxn * 4];
inline int ls(int x) { return x << 1; }
inline int rs(int x) { return x << 1 | 1; }
inline void push_up(int rt) {
s[rt] = s[ls(rt)] + s[rs(rt)];
s[rt] %= mod;
}
inline void push_down(int rt, int le) {
if (lz[rt]) {
lz[ls(rt)] += lz[rt];
lz[rs(rt)] += lz[rt];
s[ls(rt)] += lz[rt] * (le - (le >> 1));
s[rs(rt)] += lz[rt] * (le >> 1);
s[ls(rt)] %= mod;
s[rs(rt)] %= mod;
lz[rt] = 0;
}
}
void build(int rt, int l, int r, long long arr[]) {
if (l == r) {
s[rt] = arr[l];
s[rt] %= mod;
return;
}
int mid = (l + r) >> 1;
build(ls(rt), l, mid, arr);
build(rs(rt), mid + 1, r, arr);
push_up(rt);
}
void upd(int rt, int l, int r, int tl, int tr, long long k) {
if (tl > tr) return;
if (l >= tl && r <= tr) {
s[rt] += k * (r - l + 1);
s[rt] %= mod;
lz[rt] += k;
return;
}
push_down(rt, r - l + 1);
int mid = (l + r) >> 1;
if (tl <= mid) upd(ls(rt), l, mid, tl, tr, k);
if (tr > mid) upd(rs(rt), mid + 1, r, tl, tr, k);
push_up(rt);
}
long long ask(int rt, int l, int r, int tl, int tr) {
if (tl > tr) return 0l;
if (l == tl && r == tr)
return s[rt];
push_down(rt, r - l + 1);
int mid = (l + r) >> 1;
if (tr <= mid) return ask(ls(rt), l, mid, tl, tr);
if (tl > mid) return ask(rs(rt), mid + 1, r, tl, tr);
return (ask(ls(rt), l, mid, tl, mid) + ask(rs(rt), mid + 1, r, mid + 1, tr)) % mod;
}