#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline T abs(T a) {
  return ((a < 0) ? -a : a);
}
template <typename T>
inline T sqr(T a) {
  return a * a;
}
const long long MOD = 1e9 + 9;
long long sum(long long a, long long b) { return (a + b) % MOD; }
pair<long long, long long> sum(const pair<long long, long long>& a,
                               const pair<long long, long long>& b) {
  return pair<long long, long long>(sum(a.first, b.first),
                                    sum(a.second, b.second));
}
typedef long long mat[2][2];
typedef long long mat3[3][3];
pair<long long, long long> mul(pair<long long, long long> a, mat m) {
  pair<long long, long long> res;
  res.first = (m[0][0] * a.first + m[0][1] * a.second) % MOD;
  res.second = (m[1][0] * a.first + m[1][1] * a.second) % MOD;
  return res;
}
void mul(mat a, mat b, mat res) {
  for (int i = int(0); i < int(2); ++i)
    for (int j = int(0); j < int(2); ++j) {
      res[i][j] = 0;
      for (int t = int(0); t < int(2); ++t) {
        res[i][j] = (res[i][j] + a[i][t] * b[t][j]) % MOD;
      }
    }
}
void mul(mat3 a, mat3 b, mat3 res) {
  for (int i = int(0); i < int(3); ++i)
    for (int j = int(0); j < int(3); ++j) {
      res[i][j] = 0;
      for (int t = int(0); t < int(3); ++t) {
        res[i][j] = (res[i][j] + a[i][t] * b[t][j]) % MOD;
      }
    }
}
const int N = 300500;
const int LOG = 50;
mat fibMat[N];
mat3 sumMat[N];
int n, q;
long long a[N];
pair<long long, long long> top[4 * N];
long long t[4 * N];
int idx[N];
long long getSum(int id, pair<long long, long long> st) {
  return (sumMat[id][2][0] * st.first + sumMat[id][2][1] * st.second) % MOD;
}
void push(int v, int lf, int rg, int mid) {
  pair<long long, long long> cv = top[v];
  top[v] = pair<long long, long long>(0, 0);
  top[v * 2 + 1] = sum(top[v * 2 + 1], cv);
  t[v * 2 + 1] = sum(t[v * 2 + 1], getSum(idx[mid - lf + 1], cv));
  cv = mul(cv, fibMat[idx[mid - lf + 1]]);
  top[v * 2 + 2] = sum(top[v * 2 + 2], cv);
  t[v * 2 + 2] = sum(t[v * 2 + 2], getSum(idx[rg - mid], cv));
}
void build(int v, int lf, int rg) {
  top[v] = pair<long long, long long>(0, 0);
  if (lf == rg) {
    t[v] = a[lf] % MOD;
    return;
  }
  int mid = (lf + rg) / 2;
  build(v * 2 + 1, lf, mid);
  build(v * 2 + 2, mid + 1, rg);
  t[v] = sum(t[v * 2 + 1], t[v * 2 + 2]);
}
void add(int from, int to, pair<long long, long long>& val, int v, int lf,
         int rg) {
  if (from == lf && to == rg) {
    top[v] = sum(top[v], val);
    t[v] = sum(t[v], getSum(idx[rg - lf + 1], val));
    val = mul(val, fibMat[idx[rg - lf + 1]]);
  } else {
    int mid = (lf + rg) / 2;
    push(v, lf, rg, mid);
    if (from <= mid) add(from, min(to, mid), val, v * 2 + 1, lf, mid);
    if (to > mid) add(max(from, mid + 1), to, val, v * 2 + 2, mid + 1, rg);
    t[v] = sum(t[v * 2 + 1], t[v * 2 + 2]);
  }
}
long long get(int from, int to, int v, int lf, int rg) {
  if (from == lf && to == rg) return t[v];
  int mid = (lf + rg) / 2;
  push(v, lf, rg, mid);
  long long res = 0;
  if (from <= mid) res += get(from, min(to, mid), v * 2 + 1, lf, mid);
  if (to > mid) res += get(max(from, mid + 1), to, v * 2 + 2, mid + 1, rg);
  return res % MOD;
}
void init() {
  for (int i = int(0); i < int(N); ++i) idx[i] = i - 1;
  sumMat[0][0][0] = 0;
  sumMat[0][0][1] = 1;
  sumMat[0][0][2] = 0;
  sumMat[0][1][0] = 1;
  sumMat[0][1][1] = 1;
  sumMat[0][1][2] = 0;
  sumMat[0][2][0] = 1;
  sumMat[0][2][1] = 0;
  sumMat[0][2][2] = 1;
  fibMat[0][0][0] = 0;
  fibMat[0][0][1] = 1;
  fibMat[0][1][0] = 1;
  fibMat[0][1][1] = 1;
  for (int i = 1; i < N; i++) {
    mul(sumMat[i - 1], sumMat[0], sumMat[i]);
    mul(fibMat[i - 1], fibMat[0], fibMat[i]);
  }
}
bool solve() {
  if (scanf("%d%d", &n, &q) != 2) return false;
  for (int i = int(0); i < int(n); ++i) assert(scanf("%lld", &a[i]) == 1);
  build(0, 0, n - 1);
  for (int i = int(0); i < int(q); ++i) {
    int t, lf, rg;
    assert(scanf("%d%d%d", &t, &lf, &rg) == 3);
    lf--;
    rg--;
    if (t == 1) {
      pair<long long, long long> val(1, 1);
      add(lf, rg, val, 0, 0, n - 1);
    } else
      printf("%lld\n", get(lf, rg, 0, 0, n - 1) % MOD);
  }
  return true;
}
int main() {
  init();
  while (solve()) {
  }
  return 0;
}
