#include <bits/stdc++.h>
using namespace std;
const int maxn = 300000, MOD = 1e9 + 9;
int n, m, A[maxn + 5], l[(maxn << 2) + 5], r[(maxn << 2) + 5],
    sum[(maxn << 2) + 5];
struct Matrix {
  int r, c, s[2][2];
  inline void zero(int n, int m) {
    r = n;
    c = m;
    for (int i = 0; i < r; i++)
      for (int j = 0; j < c; j++) s[i][j] = 0;
  }
  inline void unit(int n) {
    zero(n, n);
    for (int i = 0; i < n; i++) s[i][i] = 1;
  }
};
Matrix T, fst, now, s[maxn + 5], pre[maxn + 5], tag[(maxn << 2) + 5], c;
inline void AMOD(int &x, int tem) {
  if ((x += tem) >= MOD) x -= MOD;
}
inline Matrix operator+(const Matrix &a, const Matrix &b) {
  c.zero(a.r, a.c);
  for (int i = 0; i < c.r; i++)
    for (int j = 0; j < c.c; j++) AMOD(c.s[i][j] = a.s[i][j], b.s[i][j]);
  return c;
}
inline Matrix operator*(const Matrix &a, const Matrix &b) {
  c.zero(a.r, b.c);
  for (int i = 0; i < c.r; i++)
    for (int j = 0; j < c.c; j++)
      for (int k = 0; k < a.c; k++)
        AMOD(c.s[i][j], (long long)a.s[i][k] * b.s[k][j] % MOD);
  return c;
}
inline char readc() {
  static char buf[100000], *l = buf, *r = buf;
  if (l == r) r = (l = buf) + fread(buf, 1, 100000, stdin);
  if (l == r) return EOF;
  return *l++;
}
inline int readi(int &x) {
  int tot = 0, f = 1;
  char ch = readc(), lst = '+';
  while (!isdigit(ch)) {
    if (ch == EOF) return EOF;
    lst = ch;
    ch = readc();
  }
  if (lst == '-') f = -f;
  while (isdigit(ch)) tot = (tot << 3) + (tot << 1) + (ch ^ 48), ch = readc();
  return x = tot * f, ((ch) == 10 || (ch) == 13 || (ch) == EOF);
}
void Build(int L, int R, int p = 1) {
  l[p] = L;
  r[p] = R;
  tag[p].zero(1, 2);
  if (L == R) return;
  int mid = L + (R - L >> 1);
  Build(L, mid, (p << 1));
  Build(mid + 1, R, (p << 1 | 1));
}
inline void Pushdown(int p) {
  if (!tag[p].s[0][0] && !tag[p].s[0][1]) return;
  static Matrix now;
  now = tag[p];
  tag[p].zero(1, 2);
  AMOD(sum[(p << 1)], (((now)*pre[r[(p << 1)] - l[(p << 1)]]).s[0][1]));
  tag[(p << 1)] = tag[(p << 1)] + now;
  now = now * s[l[(p << 1 | 1)] - l[p]];
  AMOD(sum[(p << 1 | 1)],
       (((now)*pre[r[(p << 1 | 1)] - l[(p << 1 | 1)]]).s[0][1]));
  tag[(p << 1 | 1)] = tag[(p << 1 | 1)] + now;
}
void Insert(int L, int R, int p = 1) {
  if (R < l[p] || r[p] < L) return;
  if (L <= l[p] && r[p] <= R) {
    now = fst * s[l[p] - L];
    AMOD(sum[p], (((now)*pre[r[p] - l[p]]).s[0][1]));
    tag[p] = tag[p] + now;
    return;
  }
  Pushdown(p);
  int mid = l[p] + (r[p] - l[p] >> 1);
  Insert(L, R, (p << 1));
  Insert(L, R, (p << 1 | 1));
  AMOD(sum[p] = sum[(p << 1)], sum[(p << 1 | 1)]);
}
int Ask(int L, int R, int p = 1) {
  if (R < l[p] || r[p] < L) return 0;
  if (L <= l[p] && r[p] <= R) return sum[p];
  Pushdown(p);
  int mid = l[p] + (r[p] - l[p] >> 1), ans;
  AMOD(ans = Ask(L, R, (p << 1)), Ask(L, R, (p << 1 | 1)));
  return ans;
}
int main() {
  readi(n);
  readi(m);
  for (int i = 1, x; i <= n; i++) readi(x), AMOD(A[i] = A[i - 1], x % MOD);
  T.zero(2, 2);
  T.s[0][1] = T.s[1][0] = T.s[1][1] = 1;
  s[0].unit(2);
  pre[0] = s[0];
  for (int i = 1; i <= n; i++) s[i] = s[i - 1] * T;
  for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] + s[i];
  fst.zero(1, 2);
  fst.s[0][1] = 1;
  Build(1, n);
  for (int td, L, R, ans; m; m--) {
    readi(td);
    readi(L);
    readi(R);
    if (td == 1)
      Insert(L, R);
    else
      AMOD(ans = Ask(L, R), A[R]), AMOD(ans, MOD - A[L - 1]),
          printf("%d\n", ans);
  }
  return 0;
}
