#include <bits/stdc++.h>
using namespace std;
template <typename tn>
void read(tn& a) {
  tn x = 0, f = 1;
  char c = getchar();
  while (!isdigit(c)) {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
  a = x * f;
}
template <typename tn>
void cmax(tn& a, tn b) {
  if (b > a) a = b;
}
template <typename tn>
void cmin(tn& a, tn b) {
  if (b < a) a = b;
}
template <typename tn>
tn ABS(tn a) {
  return a < 0 ? -a : a;
}
template <typename tn>
tn SQR(tn a) {
  return a * a;
}
const int N = 330000;
const long long mod = 1000000009;
struct Node {
  int l, r;
  long long sum, f1, f2;
} t[N * 4];
int n, m;
long long a[N], F[N];
void Build(int x, int l, int r) {
  int mid = (l + r) >> 1, lc = x << 1, rc = lc + 1;
  t[x].l = l;
  t[x].r = r;
  t[x].f1 = t[x].f2 = 0;
  if (l == r) {
    t[x].sum = a[l];
    return;
  }
  Build(lc, l, mid);
  Build(rc, mid + 1, r);
  t[x].sum = (t[lc].sum + t[rc].sum) % mod;
}
inline long long getH(long long a, long long b, long long n) {
  if (n == 1) return a;
  if (n == 2) return b;
  return (a * F[n - 2] % mod + b * F[n - 1] % mod) % mod;
}
inline long long SUM(long long a, long long b, long long n) {
  if (n == 1) return a;
  if (n == 2) return (a + b) % mod;
  return (getH(a, b, n + 2) - b + mod) % mod;
}
void pushdown(int x) {
  int l = t[x].l, r = t[x].r;
  int mid = (l + r) >> 1, lc = x << 1, rc = lc + 1;
  (t[lc].f1 += t[x].f1) %= mod;
  (t[lc].f2 += t[x].f2) %= mod;
  (t[lc].sum += SUM(t[x].f1, t[x].f2, mid - l + 1)) %= mod;
  (t[rc].f1 += getH(t[x].f1, t[x].f2, mid - l + 2)) %= mod;
  (t[rc].f2 += getH(t[x].f1, t[x].f2, mid - l + 3)) %= mod;
  t[rc].sum +=
      SUM(t[x].f1, t[x].f2, r - l + 1) - SUM(t[x].f1, t[x].f2, mid - l + 1);
  (t[rc].sum += mod) %= mod;
  t[x].f1 = t[x].f2 = 0;
}
void update(int x, int l, int r, int ql, int qr) {
  int mid = (l + r) >> 1, lc = x << 1, rc = lc + 1;
  if (ql <= l && r <= qr) {
    (t[x].f1 += F[l - ql + 1]) %= mod;
    (t[x].f2 += F[l - ql + 2]) %= mod;
    (t[x].sum += SUM(F[l - ql + 1], F[l - ql + 2], r - l + 1)) %= mod;
    return;
  }
  pushdown(x);
  if (ql <= mid) update(lc, l, mid, ql, qr);
  if (qr > mid) update(rc, mid + 1, r, ql, qr);
  t[x].sum = (t[lc].sum + t[rc].sum) % mod;
  return;
}
long long query(int x, int l, int r, int ql, int qr) {
  int mid = (l + r) >> 1, lc = x << 1, rc = lc + 1;
  if (ql <= l && r <= qr) return t[x].sum;
  pushdown(x);
  if (qr <= mid)
    return query(lc, l, mid, ql, qr);
  else if (ql > mid)
    return query(rc, mid + 1, r, ql, qr);
  else
    return (query(lc, l, mid, ql, qr) + query(rc, mid + 1, r, ql, qr)) % mod;
}
int main() {
  read(n);
  read(m);
  for (int i = (1); i <= (n); i++) read(a[i]);
  F[1] = F[2] = 1;
  for (int i = (3); i <= (n + 10); i++) F[i] = (F[i - 1] + F[i - 2]) % mod;
  Build(1, 1, n);
  for (int i = (1); i <= (m); i++) {
    int tp, l, r;
    read(tp);
    read(l);
    read(r);
    if (tp == 1)
      update(1, 1, n, l, r);
    else
      printf("%I64d\n", query(1, 1, n, l, r));
  }
  return 0;
}
