#include <bits/stdc++.h>
using namespace std;
long long mod(long long a) {
  return a >= 0 ? a % 1000000009 : (1000000009 + a % 1000000009) % 1000000009;
}
long long st[2 * 3000010];
long long lz[2][2 * 3000010];
long long fib[2][3000010];
long long fibSum[2][3000010];
long long getFib(int i, long long i0, long long i1) {
  return mod(mod(fib[0][i] * i0) + mod(fib[1][i] * i1));
}
long long getFibSum(int i, long long i0, long long i1) {
  return mod(mod(fibSum[0][i] * i0) + mod(fibSum[1][i] * i1));
}
long long getFibSumRange(int i, int j, int i0, int i1) {
  if (i == 0) return getFibSum(j, i0, i1);
  return mod(getFibSum(j, i0, i1) - getFibSum(i - 1, i0, i1));
}
void buildU(vector<int> &v, int i, int l, int r) {
  if (l == r) {
    st[i] = v[l];
    return;
  }
  int m = (l + r) / 2;
  buildU(v, i << 1, l, m);
  buildU(v, i << 1 | 1, m + 1, r);
  st[i] = mod(st[i << 1] + st[i << 1 | 1]);
}
void build(vector<int> &v) {
  for (int i = 1; i < 2 * v.size(); i++) {
    lz[0][i] = 0;
    lz[1][i] = 0;
  }
  buildU(v, 1, 0, v.size() - 1);
}
const int add = 1;
bool lzEmpty(int i) { return lz[0][i] == 0 && lz[1][i] == 0; }
void lazyUpdate(int i, int l, int r) {
  st[i] = mod(st[i] + getFibSum(r - l, lz[0][i], lz[1][i]));
  if (l != r) {
    lz[0][i << 1] = mod(lz[0][i << 1] + lz[0][i]);
    lz[1][i << 1] = mod(lz[1][i << 1] + lz[1][i]);
    int m = (l + r) / 2;
    lz[0][i << 1 | 1] =
        mod(lz[0][i << 1 | 1] + getFib(m + 1 - l, lz[0][i], lz[1][i]));
    lz[1][i << 1 | 1] =
        mod(lz[1][i << 1 | 1] + getFib(m + 2 - l, lz[0][i], lz[1][i]));
  }
  lz[0][i] = 0;
  lz[1][i] = 0;
}
void changeU(int cl, int cr, int i, int l, int r) {
  if (!lzEmpty(i)) lazyUpdate(i, l, r);
  if (r < cl || cr < l) return;
  if (cl <= l && r <= cr) {
    st[i] = mod(st[i] + getFibSumRange(l - cl, r - cl, 1, 1));
    if (l != r) {
      lz[0][i << 1] = mod(lz[0][i << 1] + getFib(l - cl, 1, 1));
      lz[1][i << 1] = mod(lz[1][i << 1] + getFib(l - cl + 1, 1, 1));
      int m = (l + r) / 2;
      lz[0][i << 1 | 1] = mod(lz[0][i << 1 | 1] + getFib(m + 1 - cl, 1, 1));
      lz[1][i << 1 | 1] = mod(lz[1][i << 1 | 1] + getFib(m + 2 - cl, 1, 1));
    }
    return;
  }
  int m = (l + r) / 2;
  changeU(cl, cr, i << 1, l, m);
  changeU(cl, cr, i << 1 | 1, m + 1, r);
  st[i] = mod(st[i << 1] + st[i << 1 | 1]);
}
void change(int n, int cl, int cr) { changeU(cl, cr, 1, 0, n - 1); }
int queryU(int ql, int qr, int i, int l, int r) {
  if (!lzEmpty(i)) lazyUpdate(i, l, r);
  if (r < ql || qr < l) return 0;
  if (ql <= l && r <= qr) return st[i];
  int m = (l + r) / 2;
  int q1 = queryU(ql, qr, i << 1, l, m);
  int q2 = queryU(ql, qr, i << 1 | 1, m + 1, r);
  return mod(q1 + q2);
}
int query(int n, int ql, int qr) { return queryU(ql, qr, 1, 0, n - 1); }
void print(int n) {
  cout << "st" << endl;
  for (int i = 1; i < 2 * n; i++) {
    cout << setw(4) << st[i] << " ";
  }
  cout << endl;
  for (int j = 0; j < 2; j++) {
    cout << "lz[" << j << "]" << endl;
    for (int i = 1; i < 2 * n; i++) {
      cout << setw(4) << lz[j][i] << " ";
    }
    cout << endl;
  }
  cout << endl;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n, m;
  cin >> n >> m;
  fib[0][0] = 1;
  fib[0][1] = 0;
  fib[1][0] = 0;
  fib[1][1] = 1;
  fibSum[0][0] = fib[0][0];
  fibSum[1][0] = fib[1][0];
  for (int j = 0; j < 2; j++) {
    for (int i = 2; i < n; i++) {
      fib[j][i] = (fib[j][i - 2] + fib[j][i - 1]) % 1000000009;
    }
  }
  for (int j = 0; j < 2; j++) {
    for (int i = 0; i < n; i++) {
      fibSum[j][i] = (fibSum[j][i - 1] + fib[j][i]) % 1000000009;
    }
  }
  vector<int> v;
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    v.push_back(x);
  }
  build(v);
  for (int i = 0; i < m; i++) {
    int op, l, r;
    cin >> op >> l >> r;
    l--;
    r--;
    if (op == 1) {
      change(n, l, r);
    } else {
      cout << query(n, l, r) << endl;
    }
  }
  return 0;
}
