#include <bits/stdc++.h>
using namespace std;
const int N = 300010;
const int S = 547;
const int MOD = (int)1e9 + 9;
int f[N];
int a[N];
int b[N];
int res[N];
vector<pair<int, int> > q;
inline void ADD(int &ref, const int &v) {
  ref += v;
  if (ref >= MOD) ref -= MOD;
}
inline void upd(int &ref) {
  if (ref < 0) ref += MOD;
  if (ref >= MOD) ref -= MOD;
}
void pre() {
  f[1] = f[2] = 1;
  for (int i = 3; i < N; i++) {
    f[i] = f[i - 1] + f[i - 2];
    if (f[i] >= MOD) f[i] -= MOD;
  }
}
inline int get(int x) { return f[x + 2] - 1; }
inline int get(int l, int r) { return (get(r) - get(l - 1) + MOD) % MOD; }
inline int query(int l, int r) {
  int res = 0;
  for (auto &x : q) {
    if (l <= x.second && r >= x.first) {
      ADD(res,
          get(max(l, x.first) - x.first + 1, min(x.second, r) - x.first + 1));
    }
  }
  return res;
}
int main() {
  cin.sync_with_stdio(0);
  cin.tie(0);
  pre();
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    res[i] = a[i];
    if (i > 0) {
      ADD(res[i], res[i - 1]);
    }
  }
  for (int i = 0; i < m; i++) {
    int t, l, r;
    cin >> t >> l >> r;
    l--;
    r--;
    if (t == 1) {
      ADD(b[l], 1);
      b[r + 1] -= f[r - l + 2];
      b[r + 2] -= f[r - l + 1];
      upd(b[r + 1]);
      upd(b[r + 2]);
      q.push_back({l, r});
    } else {
      int ans = res[r] + MOD - (l > 0 ? res[l - 1] : 0);
      if (ans >= MOD) ans -= MOD;
      ADD(ans, query(l, r));
      cout << ans << '\n';
    }
    if (i % S == 0) {
      for (int i = 0; i < n; i++) {
        if (i > 0) ADD(b[i], b[i - 1]);
        if (i > 1) ADD(b[i], b[i - 2]);
        ADD(a[i], b[i]);
        res[i] = a[i];
        if (i > 0) ADD(res[i], res[i - 1]);
      }
      fill(b, b + n, 0);
      q.clear();
    }
  }
  exit(0);
}
