#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000009;
void sync_stdio() {
  cin.tie(NULL);
  ios_base::sync_with_stdio(false);
}
struct Sync_stdio {
  Sync_stdio() {
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
  }
} _sync_stdio;
struct FAIL {
  FAIL() {
    cout << "CHANGE!!!"
         << "\n";
  }
};
class Fib {
  vector<int> fib;

 public:
  Fib(int n) {
    fib.resize(n);
    fib[0] = 0;
    fib[1] = 1;
    for (int i = (2); i < (n); ++i) {
      fib[i] = (fib[i - 1] + fib[i - 2]) % MOD;
    }
  }
  int get_fib(int a, int b, int pos) {
    return ((long long)(b - a + MOD) * fib[pos] + (long long)a * fib[pos + 1]) %
           MOD;
  }
  int get_sum(int a, int b, int l, int r) {
    return (get_fib(a, b, r + 2) - get_fib(a, b, l + 1) + MOD) % MOD;
  }
};
Fib fib(500000);
template <class T = int>
class SegmentTree {
  int maxn = 150000;
  vector<T> t;
  vector<pair<int, int> > delta;
  vector<int> tl;
  vector<int> tr;
  vector<int> dflag;
  void build(vector<T> &a, int v, int tleft, int tright) {
    tl[v] = tleft;
    tr[v] = tright;
    if (tleft == tright) {
      if (tleft < a.size()) {
        t[v] = a[tleft];
      }
    } else {
      int tmid = (tleft + tright) / 2;
      build(a, v * 2 + 1, tleft, tmid);
      build(a, v * 2 + 2, tmid + 1, tright);
      t[v] = (t[v * 2 + 1] + t[v * 2 + 2]) % MOD;
    }
  }
  void change(int v, pair<int, int> x) {
    delta[v].first = (delta[v].first + x.first) % MOD;
    delta[v].second = (delta[v].second + x.second) % MOD;
    t[v] = (t[v] + fib.get_sum(x.first, x.second, 0, tr[v] - tl[v])) % MOD;
    dflag[v] = 1;
  }
  void update(int v, int l, int r, T x) {
    if (l > r) {
      return;
    }
    push(v);
    if (l == tl[v] && tr[v] == r) {
      change(v, {fib.get_fib(0, 1, x), fib.get_fib(0, 1, x + 1)});
    } else {
      int tm = (tl[v] + tr[v]) / 2;
      update(v * 2 + 1, l, min(r, tm), x);
      update(v * 2 + 2, max(l, tm + 1), r, x + max(0, tl[v * 2 + 2] - l));
      t[v] = (t[2 * v + 1] + t[2 * v + 2]) % MOD;
    }
  }
  void push(int v) {
    if (dflag[v] != 0) {
      if (tl[v] != tr[v]) {
        change(2 * v + 1, delta[v]);
        int f1 =
            fib.get_fib(delta[v].first, delta[v].second, tl[v * 2 + 2] - tl[v]);
        int f2 = fib.get_fib(delta[v].first, delta[v].second,
                             tl[v * 2 + 2] - tl[v] + 1);
        change(2 * v + 2, {f1, f2});
      }
      delta[v] = {0, 0};
      dflag[v] = 0;
    }
  }
  long long sum(int v, int l, int r) {
    if (l > r) {
      return 0;
    }
    push(v);
    if (l == tl[v] && r == tr[v]) {
      return t[v];
    }
    int tm = (tl[v] + tr[v]) / 2;
    return (sum(v * 2 + 1, l, min(r, tm)) + sum(v * 2 + 2, max(l, tm + 1), r)) %
           MOD;
  }
  void build(vector<T> &a) { build(a, 0, 0, maxn - 1); }

 public:
  int size() { return maxn; }
  SegmentTree(vector<T> &a) {
    maxn = a.size();
    t.resize(4 * maxn);
    delta.resize(4 * maxn);
    tl.resize(4 * maxn);
    tr.resize(4 * maxn);
    dflag.resize(4 * maxn);
    build(a);
  }
  void update(int l, int r) { update(0, l, r, 1); }
  long long sum(int l, int r) { return sum(0, l, r); }
  T operator[](int x) { return sum(x, x); }
};
int main() {
  int n, q;
  cin >> n >> q;
  vector<int> v(n);
  for (int __i = 0; __i < (n); ++__i) cin >> v[__i];
  ;
  SegmentTree<int> tree(v);
  for (int i = (0); i < (q); ++i) {
    int t, l, r;
    cin >> t >> l >> r;
    --l, --r;
    if (t == 1) {
      tree.update(l, r);
    } else {
      cout << tree.sum(l, r) << "\n";
    }
  }
  return 0;
}
