#include <bits/stdc++.h>
using namespace std;
int n, m, a[300005], op, l, r;
long long fib[300005 + 100];
struct wyh {
  long long tagl, tagr, sum;
} tree[300005 * 4];
inline long long getint() {
  long long x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
  return x * f;
}
inline void update(int x) {
  tree[x].sum = tree[x * 2].sum + tree[x * 2 + 1].sum;
  if (tree[x].sum >= 1000000009) tree[x].sum %= 1000000009;
}
inline void build(int x, int l, int r) {
  if (l == r) {
    tree[x].sum = a[l];
    return;
  }
  int mid = (l + r) >> 1;
  build(x * 2, l, mid), build(x * 2 + 1, mid + 1, r);
  update(x);
}
inline void modify(int x, int l, int r, int s, int t, int c, int d);
inline void push(int x, int l, int r) {
  if (tree[x].tagl || tree[x].tagr) {
    int mid = (l + r) >> 1;
    modify(x * 2, l, mid, l, r, tree[x].tagl, tree[x].tagr);
    modify(x * 2 + 1, mid + 1, r, l, r, tree[x].tagl, tree[x].tagr);
    tree[x].tagl = tree[x].tagr = 0;
  }
}
inline long long get(int a, int b, int x) {
  if (x == 0) return a;
  if (x == 1) return b;
  return (a * fib[x - 1] % 1000000009 + b * fib[x] % 1000000009) % 1000000009;
}
inline void modify(int x, int l, int r, int s, int t, int c, int d) {
  if (s <= l && t >= r) {
    int first, second;
    first = get(c, d, l - s), second = get(c, d, l - s + 1);
    c = first, d = second;
    tree[x].tagl += c, tree[x].tagr += d;
    tree[x].tagl %= 1000000009, tree[x].tagr %= 1000000009;
    tree[x].sum = (tree[x].sum + get(c, d, r - l + 2) - d) % 1000000009;
    return;
  }
  push(x, l, r);
  int mid = (l + r) >> 1;
  if (s <= mid) modify(x * 2, l, mid, s, t, c, d);
  if (t > mid) modify(x * 2 + 1, mid + 1, r, s, t, c, d);
  update(x);
}
inline long long query(int x, int l, int r, int s, int t) {
  if (s <= l && t >= r) return tree[x].sum;
  int mid = (l + r) >> 1;
  push(x, l, r);
  long long tmp = 0;
  if (s <= mid) tmp += query(x * 2, l, mid, s, t);
  if (t > mid) tmp += query(x * 2 + 1, mid + 1, r, s, t);
  return tmp;
}
void work() {
  n = getint(), m = getint();
  for (int i = 1; i <= n; ++i) a[i] = getint();
  fib[1] = 1;
  for (int i = 2; i <= n + 5; ++i)
    fib[i] = (fib[i - 1] + fib[i - 2]) % 1000000009;
  build(1, 1, n);
  for (int i = 1; i <= m; ++i) {
    op = getint(), l = getint(), r = getint();
    if (op == 1)
      modify(1, 1, n, l, r, 1, 1);
    else
      printf("%I64d\n",
             (query(1, 1, n, l, r) % 1000000009 + 1000000009) % 1000000009);
  }
}
int main() {
  work();
  return 0;
}
