#include <bits/stdc++.h>
using namespace std;
template <typename T>
using min_queue = priority_queue<T, vector<T>, greater<T>>;
const long long MOD = 1e9 + 9;
inline long long pw(long long a, long long b) {
  a %= MOD;
  long long res = 1;
  for (; b; b >>= 1) {
    if (b & 1) res = res * a % MOD;
    a = a * a % MOD;
  }
  return res;
}
inline long long inv(long long a) { return pw(a, MOD - 2); }
const long long sq5 = 383008016;
const long long isq5 = inv(sq5);
const long long aa = (sq5 + 1 + MOD) / 2;
const long long bb = (-sq5 + 1 + MOD) / 2;
int N;
int a[300300];
struct segtree {
  using T = long long;
  struct node {
    long long a = 0, b = 0;
    long long sa = 0, sb = 0;
    long long s = 0;
  };
  int N;
  vector<node> seg;
  segtree(int NN) : N(NN), seg(4 * (N + 1)) {}
  inline node combine(node l, node r) {
    l.s += r.s;
    l.sa += r.sa;
    l.sb += r.sb;
    if (l.s >= MOD) l.s -= MOD;
    if (l.sa >= MOD) l.sa -= MOD;
    if (l.sb >= MOD) l.sb -= MOD;
    return l;
  }
  void build(int ix, int l, int r) {
    if (r - l == 1) {
      seg[ix].s = a[l];
      seg[ix].sa = pw(aa, l + 1) * isq5 % MOD;
      seg[ix].sb = pw(bb, l + 1) * isq5 % MOD;
      return;
    }
    build(ix * 2, l, (l + r) / 2);
    build(ix * 2 + 1, (l + r) / 2, r);
    seg[ix] = combine(seg[2 * ix], seg[2 * ix + 1]);
  }
  void build() { build(1, 0, N); }
  inline void push(int ix, int l, int r) {
    if (seg[ix].a == 0 && seg[ix].b == 0) return;
    if (r - l > 1) {
      seg[2 * ix].a += seg[ix].a;
      if (seg[2 * ix].a >= MOD) seg[2 * ix].a -= MOD;
      seg[2 * ix].b += seg[ix].b;
      if (seg[2 * ix].b >= MOD) seg[2 * ix].b -= MOD;
      seg[2 * ix + 1].a += seg[ix].a;
      if (seg[2 * ix + 1].a >= MOD) seg[2 * ix + 1].a -= MOD;
      seg[2 * ix + 1].b += seg[ix].b;
      if (seg[2 * ix + 1].b >= MOD) seg[2 * ix + 1].b -= MOD;
    }
    seg[ix].s += seg[ix].a * seg[ix].sa % MOD;
    seg[ix].s -= seg[ix].b * seg[ix].sb % MOD;
    if (seg[ix].s >= MOD) seg[ix].s -= MOD;
    if (seg[ix].s < 0) seg[ix].s += MOD;
    seg[ix].a = seg[ix].b = 0;
  }
  void update(int a, int b, int ix, int l, int r) {
    push(ix, l, r);
    if (b <= l || a >= r) return;
    if (a <= l && r <= b) {
      seg[ix].a += pw(aa, MOD - 1 - a);
      seg[ix].b += pw(bb, MOD - 1 - a);
      if (seg[ix].a >= MOD) seg[ix].a -= MOD;
      if (seg[ix].b >= MOD) seg[ix].b -= MOD;
      push(ix, l, r);
      return;
    }
    update(a, b, 2 * ix, l, (l + r) / 2);
    update(a, b, 2 * ix + 1, (l + r) / 2, r);
    seg[ix] = combine(seg[2 * ix], seg[2 * ix + 1]);
  }
  void update(int a, int b) { update(a, b, 1, 0, N); }
  long long query(int a, int b, int ix, int l, int r) {
    push(ix, l, r);
    if (b <= l || a >= r) return 0;
    if (a <= l && r <= b) {
      return seg[ix].s;
    }
    long long resl = query(a, b, 2 * ix, l, (l + r) / 2);
    long long resr = query(a, b, 2 * ix + 1, (l + r) / 2, r);
    return (resl + resr) % MOD;
  }
  T query(int a, int b) { return query(a, b, 1, 0, N); }
};
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> N;
  int M;
  cin >> M;
  for (int i = 0; i < N; i++) cin >> a[i];
  segtree seg(N);
  seg.build();
  while (M-- > 0) {
    int op, l, r;
    cin >> op >> l >> r;
    if (op == 1) {
      seg.update(l - 1, r);
    } else {
      cout << seg.query(l - 1, r) << '\n';
    }
  }
  return 0;
}
