由于有强迫症所以小号JamEater关。

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define endl '\n'
#define debug(x) cerr << #x << " = " << x << endl
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define per(i, a, b) for (int i = (a); i >= (b); i--)
#define gn(u, v) for (int v : G.G[u])
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define pii pair<int, int>
#define vi vector<int>
#define vpii vector<pii>
#define vvi vector<vi>
#define no cout << "NO" << endl
#define yes cout << "YES" << endl
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define tomin(x, y) ((x) = min((x), (y)))
#define tomax(x, y) ((x) = max((x), (y)))
#define ck(mask, i) (((mask) >> (i)) & 1)
#define pq priority_queue

constexpr int MOD = 1e9 + 9;
constexpr int MAXN = 3e5 + 5;

int qpow(int x, int y) {
    int res = 1;
    while (y) {
        if (y & 1)
            res = res * x % MOD;
        x = x * x % MOD;
        y >>= 1;
    }
    return res;
}

struct Mint {
    int x;
    Mint() { x = 0; }
    Mint(const int _x) { x = _x % MOD; }
    friend Mint operator+(Mint x, Mint y) {
        int t = x.x + y.x;
        return (t >= MOD) ? (t - MOD) : t;
    }
    friend Mint operator-(Mint x, Mint y) {
        int t = x.x - y.x;
        return (t < 0) ? (t + MOD) : t;
    }
    friend Mint operator*(Mint x, Mint y) {
        return x.x * y.x % MOD;
    }
    friend Mint operator/(Mint x, Mint y) {
        return x.x * qpow(y.x, MOD - 2) % MOD;
    }
    friend Mint operator^(Mint& x, int y) {
        return Mint(qpow(x.x, y));
    }
    friend Mint& operator+=(Mint& x, Mint y) {
        return x = x + y;
    }
    friend Mint& operator-=(Mint& x, Mint y) {
        return x = x - y;
    }
    friend Mint& operator*=(Mint& x, Mint y) {
        return x = x * y;
    }
    friend Mint& operator/=(Mint& x, Mint y) {
        return x = x / y;
    }
    friend Mint& operator^=(Mint& x, int y) {
        return x = x ^ y;
    }
    friend ostream& operator<<(ostream& o, Mint y) {
        o << y.x;
        return o;
    }
    friend istream& operator>>(istream& i, Mint& y) {
        i >> y.x;
        return i;
    }
    Mint& operator++() {
        x++;
        if (x >= MOD)
            x -= MOD;
        return *this;
    }
    Mint operator++(signed) {
        x++;
        if (x >= MOD)
            x -= MOD;
        return *this;
    }
    Mint& operator--() {
        x--;
        if (x < 0)
            x += MOD;
        return *this;
    }
    Mint operator--(signed) {
        x--;
        if (x < 0)
            x += MOD;
        return *this;
    }
    friend bool operator==(const Mint& x, const Mint &y) {
        return x.x == y.x;
    }
    friend bool operator!=(const Mint& x, const Mint &y) {
        return x.x == y.x;
    }
};

const Mint C1 = 276601605;
const Mint C2 = 691504013;
const Mint C3 = 308495997;

int n, m;
Mint a[MAXN];
Mint powC2[MAXN], powC3[MAXN];

struct SegTree {
    struct Node {
        int l, r;
        Mint sum, lz1, lz2;
    } tr[MAXN << 2];

    void lazy1(int k, Mint v) {
        tr[k].lz1 += v;
        int len = tr[k].r - tr[k].l + 1;
        tr[k].sum += v * (powC2[len + 1] - C2) / (C2 - 1);
    }

    void lazy2(int k, Mint v) {
        tr[k].lz2 += v;
        int len = tr[k].r - tr[k].l + 1;
        tr[k].sum += v * (powC3[len + 1] - C3) / (C3 - 1);
    }

    void push(int k) {
        int lc = k * 2;
        int rc = lc + 1;
        int llen = tr[lc].r - tr[lc].l + 1;
        if (tr[k].lz1 != 0) {
            lazy1(lc, tr[k].lz1);
            lazy1(rc, tr[k].lz1 * powC2[llen]);
            tr[k].lz1 = 0;
        }
        if (tr[k].lz2 != 0) {
            lazy2(lc, tr[k].lz2);
            lazy2(rc, tr[k].lz2 * powC3[llen]);
            tr[k].lz2 = 0;
        }
    }

    void pull(int k) {
        int lc = k * 2;
        int rc = lc + 1;
        tr[k].sum = tr[lc].sum + tr[rc].sum;
    }

    void build(int k, int l, int r) {
        tr[k] = { l, r, a[l], 0, 0 };
        // cerr << k << " " << tr[k].sum << endl;
        if (l == r) {
            return;
        }
        int md = l + r >> 1;
        int lc = k * 2;
        int rc = lc + 1;
        build(lc, l, md);
        build(rc, md + 1, r);
        pull(k);
    }
    
    void update1(int k, int l, int r, Mint v) {
        if (tr[k].l >= l && tr[k].r <= r) {
            return lazy1(k, v);
        }
        push(k);
        int md = tr[k].l + tr[k].r >> 1;
        int lc = k * 2;
        int rc = lc + 1;
        if (r <= md) {
            update1(lc, l, r, v);
        } else if (l > md) {
            update1(rc, l, r, v);
        } else {
            update1(lc, l, md, v);
            update1(rc, md + 1, r, v * powC2[md - l + 1]);
        }
        pull(k);
    }

    void update2(int k, int l, int r, Mint v) {
        if (tr[k].l >= l && tr[k].r <= r) {
            return lazy2(k, v);
        }
        push(k);
        int md = tr[k].l + tr[k].r >> 1;
        int lc = k * 2;
        int rc = lc + 1;
        if (r <= md) {
            update2(lc, l, r, v);
        } else if (l > md) {
            update2(rc, l, r, v);
        } else {
            update2(lc, l, md, v);
            update2(rc, md + 1, r, v * powC3[md - l + 1]);
        }
        pull(k);
    }

    Mint query(int k, int l, int r) {
        // cerr << "?" << k << " " << tr[k].l << " " << tr[k].r << " " << l << " " << r << endl;
        // cerr << "!" << k << endl;
        if (tr[k].l >= l && tr[k].r <= r) {
            return tr[k].sum;
        }
        push(k);
        int md = tr[k].l + tr[k].r >> 1;
        int lc = k * 2;
        int rc = lc + 1;
        if (r <= md) {
            return query(lc, l, r);
        } else if (l > md) {
            return query(rc, l, r);
        } else {
            return query(lc, l, md) + query(rc, md + 1, r);
        }
    }
} seg;

signed main() {
    // ios::sync_with_stdio(false);
    // cin.tie(0);
    // cout.tie(0);

    cin >> n >> m;
    rep(i, 1, n) {
        // cerr << i << endl;
        cin >> a[i];
        // cerr << a[i] << endl;
    }

    powC2[0] = powC3[0] = 1;
    rep(i, 1, n + 2) {
        powC2[i] = powC2[i - 1] * C2;
        powC3[i] = powC3[i - 1] * C3;
    }

    seg.build(1, 1, n);
    // cerr << endl;

    // cerr << seg.query(1, 1, n) << endl;

    while (m--) {
        int opt, l, r;
        cin >> opt >> l >> r;
        if (opt == 1) {
            seg.update1(1, l, r, C1);
            seg.update2(1, l, r, 0 - C1);
        } else {
            cout << seg.query(1, l, r) << endl;
        }
        // rep(i, 1, n) {
        //     cerr << seg.query(1, i, i) << " ";
        // }
        // cerr << endl;
    }

    return 0;
}