#include <bits/stdc++.h>
using namespace std;
long long const mod = 1e9 + 9;
struct matrix {
  int n, m;
  long long num[2][2];
};
inline matrix operator*(const matrix& A, const matrix& B) {
  matrix C;
  C.n = A.n;
  C.m = B.m;
  for (int i = 0; i < C.n; ++i) {
    for (int j = 0; j < C.m; ++j) {
      C.num[i][j] = 0;
      for (int k = 0; k < A.m; ++k) {
        C.num[i][j] += A.num[i][k] * B.num[k][j];
        C.num[i][j] %= mod;
      }
    }
  }
  return C;
}
int const N_MAX = 500000, M_MAX = 2000000;
int n, m;
int a[N_MAX];
long long f[N_MAX];
matrix tran[N_MAX];
inline void prepare() {
  f[1] = f[2] = 1;
  for (int i = 3; i <= n + 10; ++i) {
    f[i] = f[i - 1] + f[i - 2];
    if (f[i] >= mod) {
      f[i] -= mod;
    }
  }
  tran[1].n = tran[1].m = 2;
  tran[1].num[0][0] = tran[1].num[0][1] = tran[1].num[1][0] = 1;
  tran[1].num[1][1] = 0;
  for (int i = 2; i <= n + 10; ++i) {
    tran[i] = tran[1] * tran[i - 1];
  }
}
inline void build(int u, int l, int r);
inline void edit(int u, int l, int r, int c);
inline long long query(int u, int l, int r);
int main() {
  scanf("%d%d", &n, &m);
  prepare();
  for (int i = 1; i <= n; ++i) {
    scanf("%d", a + i);
  }
  build(1, 1, n);
  for (int i = 1; i <= m; ++i) {
    int type, l, r;
    scanf("%d%d%d", &type, &l, &r);
    if (type == 1) {
      edit(1, l, r, l);
    } else {
      printf("%d\n", (int)query(1, l, r));
    }
  }
  return 0;
}
inline long long get_num(const long long& a1, const long long& a2, int n) {
  if (n == 1) {
    return a1;
  }
  if (n == 2) {
    return a2;
  }
  static matrix nums, ans;
  nums.n = 2;
  nums.m = 1;
  nums.num[0][0] = a2;
  nums.num[1][0] = a1;
  ans = tran[n - 1] * nums;
  return ans.num[1][0];
}
inline long long get_sum(const long long& a1, const long long& a2, int n) {
  if (n == 1) {
    return a1;
  }
  if (n == 2) {
    return (a1 + a2) % mod;
  }
  long long ans = get_num(a1, a2, n + 2) - a2;
  if (ans < 0) {
    ans += mod;
  }
  if (ans >= mod) {
    ans -= mod;
  }
  return ans;
}
int LEFT[M_MAX], RIGHT[M_MAX];
long long data[M_MAX], tag1[M_MAX], tag2[M_MAX];
inline void cover(int u, int start) {
  int leftpos = LEFT[u];
  int length = leftpos - start + 1;
  long long t1 = f[length], t2 = f[length + 1];
  tag1[u] += t1;
  tag2[u] += t2;
  data[u] += get_sum(t1, t2, RIGHT[u] - LEFT[u] + 1);
  if (tag1[u] >= mod) {
    tag1[u] -= mod;
  }
  if (tag2[u] >= mod) {
    tag2[u] -= mod;
  }
  if (data[u] >= mod) {
    data[u] -= mod;
  }
}
inline void update(int u) {
  data[u] = data[u << 1] + data[u << 1 | 1];
  if (data[u] >= mod) {
    data[u] -= mod;
  }
}
inline void push(int u) {
  if (tag1[u] > 0 || tag2[u] > 0) {
    int leftson = u << 1;
    int rightson = u << 1 | 1;
    int length = RIGHT[leftson] - LEFT[leftson] + 1;
    tag1[leftson] += tag1[u];
    tag2[leftson] += tag2[u];
    data[leftson] +=
        get_sum(tag1[u], tag2[u], RIGHT[leftson] - LEFT[leftson] + 1);
    long long t1 = get_num(tag1[u], tag2[u], length + 1);
    long long t2 = get_num(tag1[u], tag2[u], length + 2);
    tag1[rightson] += t1;
    tag2[rightson] += t2;
    data[rightson] += get_sum(t1, t2, RIGHT[rightson] - LEFT[rightson] + 1);
    if (tag1[leftson] >= mod) {
      tag1[leftson] -= mod;
    }
    if (tag2[leftson] >= mod) {
      tag2[leftson] -= mod;
    }
    if (data[leftson] >= mod) {
      data[leftson] -= mod;
    }
    if (tag1[rightson] >= mod) {
      tag1[rightson] -= mod;
    }
    if (tag2[rightson] >= mod) {
      tag2[rightson] -= mod;
    }
    if (data[rightson] >= mod) {
      data[rightson] -= mod;
    }
    tag1[u] = tag2[u] = 0;
  }
}
inline void edit(int u, int l, int r, int c) {
  if (l <= LEFT[u] && RIGHT[u] <= r) {
    cover(u, c);
    return;
  }
  push(u);
  if (l <= RIGHT[u << 1]) {
    edit(u << 1, l, r, c);
  }
  if (LEFT[u << 1 | 1] <= r) {
    edit(u << 1 | 1, l, r, c);
  }
  update(u);
}
inline long long query(int u, int l, int r) {
  if (l <= LEFT[u] && RIGHT[u] <= r) {
    return data[u];
  }
  push(u);
  long long ans = 0;
  if (l <= RIGHT[u << 1]) {
    ans += query(u << 1, l, r);
  }
  if (LEFT[u << 1 | 1] <= r) {
    ans += query(u << 1 | 1, l, r);
  }
  if (ans >= mod) {
    ans -= mod;
  }
  return ans;
}
inline void build(int u, int l, int r) {
  LEFT[u] = l, RIGHT[u] = r;
  if (l == r) {
    data[u] = a[l];
  } else {
    int m = l + r >> 1;
    build(u << 1, l, m);
    build(u << 1 | 1, m + 1, r);
    update(u);
  }
}
