#include <bits/stdc++.h>
using namespace std;
using pi = pair<long long, long long>;
const int MOD = 1e9 + 9, MAX = 3e5 + 5;
int n;
long long a[MAX], fib[MAX];
long long add(long long x, long long y) {
  x += y;
  if (x >= MOD) {
    x -= MOD;
  }
  return x;
}
void add_self(long long& x, long long y) { x = add(x, y); }
void add_self(pi& x, long long one, long long two) {
  x.first = add(x.first, one);
  x.second = add(x.second, two);
}
long long sub(long long x, long long y) {
  x -= y;
  if (x < 0) {
    x += MOD;
  }
  return x;
}
struct ST {
  long long tree[MAX << 2];
  pi lazy[MAX << 2];
  void build(int id = 1, int l = 0, int r = n) {
    if (l + 1 == r) {
      tree[id] = a[l];
      return;
    }
    int m = (l + r) >> 1;
    build(id << 1, l, m);
    build(id << 1 | 1, m, r);
    tree[id] = add(tree[id << 1], tree[id << 1 | 1]);
  }
  void push(int id, int l, int r) {
    if (lazy[id] == pi{0, 0}) return;
    if (l + 1 != r) {
      int m = (l + r) >> 1;
      long long one = lazy[id].first, two = lazy[id].second;
      long long n_one = (one * fib[m - l - 1] + two * fib[m - l]) % MOD;
      long long n_two = (one * fib[m - l] + two * fib[m - l + 1]) % MOD;
      long long uwu = (n_one * fib[r - m] + n_two * fib[r - m + 1]) % MOD;
      add_self(lazy[id << 1], one, two);
      add_self(lazy[id << 1 | 1], n_one, n_two);
      add_self(tree[id << 1], sub(n_two, two));
      add_self(tree[id << 1 | 1], sub(uwu, n_two));
    }
    lazy[id] = {0, 0};
  }
  long long get(int x, int y, int id = 1, int l = 0, int r = n) {
    if (r <= x || y <= l) return 0;
    if (x <= l && r <= y) return tree[id];
    int m = (l + r) >> 1;
    push(id, l, r);
    long long ga = get(x, y, id << 1, l, m);
    long long gb = get(x, y, id << 1 | 1, m, r);
    return add(ga, gb);
  }
  void upd(int x, int y, int id = 1, int l = 0, int r = n) {
    if (r <= x || y <= l) return;
    if (x <= l && r <= y) {
      long long to_tree = sub(fib[r - x + 2], fib[l - x + 2]);
      add_self(tree[id], to_tree);
      add_self(lazy[id], fib[l - x + 1], fib[l - x + 2]);
      return;
    }
    push(id, l, r);
    int m = (l + r) >> 1;
    upd(x, y, id << 1, l, m);
    upd(x, y, id << 1 | 1, m, r);
    tree[id] = add(tree[id << 1], tree[id << 1 | 1]);
  }
} T;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  fib[1] = 1;
  int m;
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    fib[i + 2] = add(fib[i + 1], fib[i]);
  }
  fib[n + 2] = add(fib[n + 1], fib[n]);
  T.build();
  while (m--) {
    char c;
    cin >> c;
    int l, r;
    cin >> l >> r;
    --l;
    if (c == '1') {
      T.upd(l, r);
    } else {
      cout << T.get(l, r) << "\n";
    }
  }
  return 0;
}
