#include <bits/stdc++.h>
using namespace std;
const double EPS = 0.0000001;
const double PI = acos(-1);
const long long INFLL = 0x7FFFFFFFFFFFFFFF;
const int INF = 0x7FFFFFFF;
template <typename T>
inline void next(T &num) {
  char c;
  num = 0;
  do {
    c = getchar_unlocked();
  } while (c != EOF && c == ' ' && c == '\n' && c == '\t');
  int sign = (c == '-' ? -1 : 1);
  if (c != '-') num += (c - '0');
  while ((c = getchar_unlocked()) != EOF && c != '\n' && c != '\t' &&
         c != ' ') {
    num *= 10;
    num += (c - '0');
  }
  num *= sign;
}
inline string getstr() {
  string str;
  char k;
  while ((k = getchar_unlocked()) == ' ' || k == '\n') {
    k = getchar_unlocked();
    if (k == ' ' || k == '\n')
      continue;
    else
      break;
  }
  str.push_back(k);
  while ((k = getchar_unlocked()) != EOF && k != '\n' && k != '\t' &&
         k != '\v' && k != '\0' && k != ' ')
    str.push_back(k);
  return str;
}
const int N = 300000, MOD = 1000000009;
int ar[N + 5], n, m;
long long F[3 * N + 3];
struct Node {
  int l, r, Mid = -1;
  long long sum, f1, f2;
  int mid() {
    if (Mid < 0) Mid = (l + r) >> 1;
    return Mid;
  }
} seg[4 * N];
long long getFib(int f1, int f2, int pos) {
  return (f1 * F[pos] % MOD + (f2 - f1) * F[pos - 1] % MOD + MOD) % MOD;
}
long long getSum(int f1, int f2, int len) {
  return (f1 * (F[len + 2] - 1) % MOD + (f2 - f1) * (F[len + 1] - 1) % MOD +
          MOD) %
         MOD;
}
void init(int l, int r, int cur) {
  seg[cur].l = l, seg[cur].r = r;
  if (l == r) {
    seg[cur].sum = ar[l];
    return;
  }
  int mid = seg[cur].mid();
  init(l, mid, (cur << 1)), init(mid + 1, r, (cur << 1 | 1));
  seg[cur].sum = (seg[(cur << 1 | 1)].sum + seg[(cur << 1)].sum + MOD) % MOD;
}
void lazy(int cur) {
  if (!seg[cur].f1 && !seg[cur].f2) return;
  seg[(cur << 1)].f1 = (seg[cur].f1 + seg[(cur << 1)].f1) % MOD;
  seg[(cur << 1)].f2 = (seg[cur].f2 + seg[(cur << 1)].f2) % MOD;
  seg[(cur << 1)].sum = (seg[(cur << 1)].sum +
                         getSum(seg[cur].f1, seg[cur].f2,
                                seg[(cur << 1)].r - seg[(cur << 1)].l + 1) +
                         MOD) %
                        MOD;
  int a = getFib(seg[cur].f1, seg[cur].f2,
                 seg[(cur << 1 | 1)].l - seg[cur].l + 1),
      b = getFib(seg[cur].f1, seg[cur].f2,
                 seg[(cur << 1 | 1)].l - seg[cur].l + 2);
  seg[(cur << 1 | 1)].f1 = (seg[(cur << 1 | 1)].f1 + a) % MOD;
  seg[(cur << 1 | 1)].f2 = (seg[(cur << 1 | 1)].f2 + b) % MOD;
  seg[(cur << 1 | 1)].sum =
      (seg[(cur << 1 | 1)].sum +
       getSum(a, b, seg[(cur << 1 | 1)].r - seg[(cur << 1 | 1)].l + 1) + MOD) %
      MOD;
  seg[cur].f1 = seg[cur].f2 = 0;
}
void upd(int l, int r, int cur) {
  if (l <= seg[cur].l && seg[cur].r <= r) {
    seg[cur].f1 = (seg[cur].f1 + F[seg[cur].l - l + 1]) % MOD;
    seg[cur].f2 = (seg[cur].f2 + F[seg[cur].l - l + 2]) % MOD;
    seg[cur].sum = (seg[cur].sum +
                    getSum(F[seg[cur].l - l + 1], F[seg[cur].l - l + 2],
                           seg[cur].r - seg[cur].l + 1) +
                    MOD) %
                   MOD;
    return;
  }
  int mid = seg[cur].mid();
  lazy(cur);
  if (l <= mid) upd(l, r, (cur << 1));
  if (r > mid) upd(l, r, (cur << 1 | 1));
  seg[cur].sum = (seg[(cur << 1)].sum + seg[(cur << 1 | 1)].sum + MOD) % MOD;
}
long long get(int l, int r, int cur) {
  if (l <= seg[cur].l && seg[cur].r <= r) return seg[cur].sum;
  int mid = seg[cur].mid();
  lazy(cur);
  long long res = 0;
  if (l <= mid) res += get(l, r, (cur << 1));
  if (res >= MOD) res -= MOD;
  if (r > mid) res += get(l, r, (cur << 1 | 1));
  if (res >= MOD) res -= MOD;
  return res;
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = int(1), _b = int(n); i <= _b; i++) scanf("%d", ar + i);
  F[1] = 1;
  for (int i = int(2), _b = int(3 * n + 2); i <= _b; i++)
    F[i] = (F[i - 1] + F[i - 2]) % MOD;
  init(1, n, 1);
  while (m--) {
    int t, l, r;
    scanf("%d%d%d", &t, &l, &r);
    if (t == 1) {
      upd(l, r, 1);
    } else {
      printf("%I64d\n", get(l, r, 1));
    }
  }
  return 0;
}
