#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10, inf = 1e9, M = 3e5 + 5;
const long long mod = 1e9 + 9;
inline int read() {
  int 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 << 3) + (x << 1) + (ch ^ 48);
    ch = getchar();
  }
  return x * f;
}
int n, m;
long long f[N];
struct Segment_Tree {
  inline void init() {
    f[0] = 0;
    f[1] = 1;
    for (int i = 2; i <= M; i++) f[i] = (f[i - 2] + f[i - 1]) % mod;
  }
  struct node {
    node *ls, *rs;
    int l, r;
    long long sum, tag, laz;
    node(int l, int r) : l(l), r(r) {
      ls = rs = NULL;
      tag = laz = sum = 0;
    }
    inline int len() { return r - l + 1; }
    inline void up() { sum = (ls->sum + rs->sum) % mod; }
    inline void add(long long a, long long b) {
      tag = (tag + a) % mod;
      laz = (laz + b) % mod;
      sum = (sum + a * f[len()] % mod + b * f[len() + 1] % mod - b) % mod;
    }
    inline void down() {
      if (!tag) return;
      long long tmpa =
          (tag * f[ls->len() - 1] % mod + laz * f[ls->len()] % mod) % mod;
      long long tmpb =
          (tag * f[ls->len()] % mod + laz * f[ls->len() + 1] % mod) % mod;
      ls->add(tag, laz);
      rs->add(tmpa, tmpb);
      tag = laz = 0;
    }
  } * root;
  Segment_Tree() { root = NULL; }
  void build(node *&p, int l, int r) {
    p = new node(l, r);
    if (p->l == p->r) return (void)(p->sum = 1ll * read() % mod);
    build(p->ls, l, ((p->l + p->r) >> 1));
    build(p->rs, ((p->l + p->r) >> 1) + 1, r);
    p->up();
  }
  long long query(node *p, int x, int y) {
    if (x <= p->l && p->r <= y) return p->sum;
    p->down();
    return ((x <= ((p->l + p->r) >> 1) ? query(p->ls, x, y) : 0) +
            (y > ((p->l + p->r) >> 1) ? query(p->rs, x, y) : 0)) %
           mod;
  }
  void chenge(node *p, int x, int y) {
    if (x <= p->l && p->r <= y)
      return (void)(p->add(f[p->l - x + 1], f[p->l - x + 2]));
    p->down();
    if (x <= ((p->l + p->r) >> 1)) chenge(p->ls, x, y);
    if (y > ((p->l + p->r) >> 1)) chenge(p->rs, x, y);
    p->up();
  }
  inline void LOL() {
    init();
    n = read();
    m = read();
    build(root, 1, n);
    for (int i = 1, opt, l, r, x; i <= m; i++) {
      opt = read();
      l = read();
      r = read();
      if (opt ^ 1)
        printf("%lld\n", (query(root, l, r) + mod) % mod);
      else
        chenge(root, l, r);
    }
  }
} DNF;
int main() {
  DNF.LOL();
  return 0;
}
