#include <bits/stdc++.h>
using namespace std;
void read_file(bool outToFile = true) {}
int n, nq;
void add(int &x, long long v) {
  x += v;
  if (x >= (1000000009)) x -= (1000000009);
}
int MAT[500000 + 9][2][2];
int SMAT[500000 + 9][2][2];
int T[2][2];
void zero(int A[2][2]) {
  for (int i = 0; i < 2; i++)
    for (int j = 0; j < 2; j++) A[i][j] = 0;
}
void identity(int A[2][2]) {
  zero(A);
  for (int i = 0; i < 2; i++) A[i][i] = 1;
}
void mult(int A[2][2], int B[2][2], int C[2][2]) {
  zero(C);
  for (int i = 0; i < 2; i++) {
    for (int j = 0; j < 2; j++) {
      for (int k = 0; k < 2; k++) {
        add(C[i][j], 1LL * A[i][k] * B[k][j] % (1000000009));
      }
    }
  }
}
void add(int A[2][2], int B[2][2], int C[2][2]) {
  zero(C);
  for (int i = 0; i < 2; i++) {
    for (int j = 0; j < 2; j++) {
      C[i][j] = A[i][j];
      add(C[i][j], B[i][j]);
    }
  }
}
void build() {
  zero(T);
  T[0][0] = 1;
  T[0][1] = 1;
  T[1][0] = 1;
  T[1][1] = 0;
  identity(MAT[0]);
  identity(SMAT[0]);
  for (int i = 1; i < 500000 + 9; i++) {
    mult(MAT[i - 1], T, MAT[i]);
    add(SMAT[i - 1], MAT[i], SMAT[i]);
  }
}
int query_F(int f0, int f1, int n) {
  int a = SMAT[n - 1][1][0];
  int b = SMAT[n - 1][1][1];
  int ret = 1LL * a * f1 % (1000000009);
  add(ret, 1LL * b * f0 % (1000000009));
  return ret;
}
int get_F(int f0, int f1, int n) {
  int a = MAT[n][1][0];
  int b = MAT[n][1][1];
  int ret = 1LL * a * f1 % (1000000009);
  add(ret, 1LL * b * f0 % (1000000009));
  return ret;
}
struct node {
  int val;
  int fst, scd;
};
node ST[3 * 500000 + 9 + 1 + 9];
int GS, GE;
void init() {
  GS = 0, GE = n - 1;
  for (int i = 0; i < 3 * 500000 + 9 + 1 + 9; i++) {
    ST[i].val = 0;
    ST[i].fst = ST[i].scd = 0;
  }
}
void merge(int p) {
  ST[p].val = ST[2 * p].val;
  add(ST[p].val, ST[2 * p + 1].val);
}
void insert(int idx, int val, int s = GS, int e = GE, int p = 1) {
  if (s == e) {
    ST[p].val = val;
    return;
  }
  int m = (s + e) / 2;
  if (idx <= m)
    insert(idx, val, s, m, 2 * p);
  else
    insert(idx, val, m + 1, e, 2 * p + 1);
  merge(p);
}
void update_node(int fst, int scd, int s, int e, int p) {
  add(ST[p].fst, fst);
  add(ST[p].scd, scd);
  add(ST[p].val, query_F(fst, scd, e - s + 1));
}
void update_child(int s, int e, int p) {
  int m = (s + e) / 2;
  int f0 = ST[p].fst, f1 = ST[p].scd;
  update_node(f0, f1, s, m, 2 * p);
  int k = m - s;
  int fkplus1 = get_F(f0, f1, k + 1);
  int fkplus2 = get_F(f0, f1, k + 2);
  update_node(fkplus1, fkplus2, m + 1, e, 2 * p + 1);
  ST[p].fst = ST[p].scd = 0;
}
void update(int fr, int to, int fst, int scd, int s = GS, int e = GE,
            int p = 1) {
  if (fr <= s && e <= to) {
    update_node(fst, scd, s, e, p);
    return;
  }
  update_child(s, e, p);
  int m = (s + e) / 2;
  if (to <= m)
    update(fr, to, fst, scd, s, m, 2 * p);
  else if (fr >= m + 1)
    update(fr, to, fst, scd, m + 1, e, 2 * p + 1);
  else {
    update(fr, to, fst, scd, s, m, 2 * p);
    int k = m - max(fr, s);
    int fkplus1 = get_F(fst, scd, k + 1);
    int fkplus2 = get_F(fst, scd, k + 2);
    update(fr, to, fkplus1, fkplus2, m + 1, e, 2 * p + 1);
  }
  merge(p);
}
void update1(int fr, int to, int s = GS, int e = GE, int p = 1) {
  if (fr <= s && e <= to) {
    int f0 = get_F(0, 1, s - fr + 1);
    int f1 = get_F(0, 1, s - fr + 1 + 1);
    update_node(f0, f1, s, e, p);
    return;
  }
  update_child(s, e, p);
  int m = (s + e) / 2;
  if (to <= m)
    update1(fr, to, s, m, 2 * p);
  else if (fr >= m + 1)
    update1(fr, to, m + 1, e, 2 * p + 1);
  else {
    update1(fr, to, s, m, 2 * p);
    update1(fr, to, m + 1, e, 2 * p + 1);
  }
  merge(p);
}
int query(int fr, int to, int s = GS, int e = GE, int p = 1) {
  if (fr <= s && e <= to) return ST[p].val;
  update_child(s, e, p);
  int m = (s + e) / 2;
  if (to <= m)
    return query(fr, to, s, m, 2 * p);
  else if (fr >= m + 1)
    return query(fr, to, m + 1, e, 2 * p + 1);
  else {
    int ql = query(fr, to, s, m, 2 * p);
    int qr = query(fr, to, m + 1, e, 2 * p + 1);
    int ret = ql;
    add(ret, qr);
    return ret;
  }
}
int main() {
  read_file();
  build();
  while (scanf("%d%d", &n, &nq) != EOF) {
    init();
    for (int i = 0; i < n; i++) {
      int x;
      scanf("%d", &x);
      insert(i, x);
    }
    while (nq--) {
      int cmd, fr, to;
      scanf("%d%d%d", &cmd, &fr, &to);
      fr--, to--;
      if (cmd == 1) {
        update1(fr, to);
        continue;
      }
      int ans = 0;
      ans = query(fr, to);
      printf("%d\n", ans);
    }
    printf("\n");
  }
}
