#include <bits/stdc++.h>
using namespace std;
const long long mod = 1000000009;
const long long A = 691504013;
const long long B = 308495997;
const long long C = 276601605;
int n, Q;
long long arr[300000 + 8], sum[300000 + 8];
long long qp(long long a, long long b) {
  long long ret = 1;
  while (b) {
    if (b & 1) ret = ret * a % mod;
    a = a * a % mod;
    b >>= 1;
  }
  return ret;
}
long long inv(long long a) { return qp(a, mod - 2); }
struct Tree {
  long long t;
  long long tre[(300000 << 2) + 8], lazy[(300000 << 2) + 8], qpt[300000 + 8],
      invt_1;
  inline long long gao(long long n) {
    return invt_1 * t % mod * (qpt[n] - 1 + mod) % mod;
  }
  void pushup(int rt) { tre[rt] = (tre[rt << 1] + tre[rt << 1 | 1]) % mod; }
  void build() {
    qpt[0] = 1;
    for (int i = 1; i <= 300000; ++i) qpt[i] = qpt[i - 1] * t % mod;
    invt_1 = qp(t - 1, mod - 2);
    memset(tre, 0, sizeof(tre));
    memset(lazy, 0, sizeof(lazy));
  }
  void pushdown(int rt, int l, int r) {
    if (!lazy[rt]) return;
    int mid = (l + r) >> 1;
    lazy[rt << 1] = (lazy[rt << 1] + lazy[rt]) % mod;
    tre[rt << 1] = (tre[rt << 1] + lazy[rt] * gao(mid - l + 1) % mod) % mod;
    lazy[rt << 1 | 1] =
        (lazy[rt << 1 | 1] + lazy[rt] * qpt[mid - l + 1] % mod) % mod;
    tre[rt << 1 | 1] = (tre[rt << 1 | 1] + lazy[rt] * gao(r - mid) % mod *
                                               qpt[mid - l + 1] % mod) %
                       mod;
    lazy[rt] = 0;
  }
  void update(int rt, int l, int r, int L, int R, long long v) {
    if (l > r) return;
    if (L <= l && r <= R) {
      lazy[rt] = (lazy[rt] + v) % mod;
      tre[rt] = (tre[rt] + v * gao(r - l + 1) % mod) % mod;
      return;
    }
    pushdown(rt, l, r);
    int mid = (l + r) >> 1;
    if (L <= mid) {
      update(rt << 1, l, mid, L, R, v);
    }
    if (mid + 1 <= R) {
      update(rt << 1 | 1, mid + 1, r, L, R, qpt[max(0, mid - L + 1)] % mod);
    }
    pushup(rt);
  }
  long long query(int rt, int l, int r, int L, int R) {
    if (l > r) return 0;
    if (L <= l && r <= R) {
      return tre[rt];
    }
    pushdown(rt, l, r);
    long long ans = 0;
    int mid = (l + r) >> 1;
    if (L <= mid) ans += query(rt << 1, l, mid, L, R);
    if (mid + 1 <= R) ans += query(rt << 1 | 1, mid + 1, r, L, R);
    return ans % mod;
  }
};
Tree t1, t2;
int main() {
  t1.t = A, t2.t = B;
  t1.build(), t2.build();
  scanf("%d %d", &n, &Q);
  for (int i = 1; i <= n; ++i) {
    scanf("%I64d", &arr[i]);
    sum[i] = (sum[i - 1] + arr[i]) % mod;
  }
  while (Q--) {
    int op, l, r;
    scanf("%d %d %d", &op, &l, &r);
    if (op == 1) {
      t1.update(1, 1, n, l, r, 1);
      t2.update(1, 1, n, l, r, 1);
    } else {
      long long ans = t1.query(1, 1, n, l, r);
      ans = (ans - t2.query(1, 1, n, l, r) + mod) % mod;
      printf("%I64d\n", (sum[r] - sum[l - 1] + mod + ans * C % mod) % mod);
    }
  }
  return 0;
}
