#include <bits/stdc++.h>
using namespace std;
const int N = 333333;
const long long mod = 1000000009ll;
int n, m;
struct node {
  int l, r;
  long long sum, f1, f2;
} t[N * 6];
long long a[N], F[N];
inline long long read() {
  long long x = 0;
  char c = getchar();
  while (!isdigit(c)) c = getchar();
  while (isdigit(c)) {
    x = x * 10ll + c - '0';
    c = getchar();
  }
  return x;
}
void calc_Fibonacci(int n) {
  F[1] = 1;
  F[2] = 1;
  for (int i = (3); i <= (N); i++) F[i] = (F[i - 1] + F[i - 2]) % mod;
}
long long calc(long long a, long long b, long long n) {
  if (n == 1)
    return a;
  else if (n == 2)
    return b;
  else
    return (a * F[n - 2] % mod + b * F[n - 1] % mod) % mod;
}
long long calc_range(long long a, long long b, long long n) {
  if (n == 1)
    return a;
  else if (n == 2)
    return (a + b) % mod;
  else
    return (calc(a, b, n + 2) - b + mod) % mod;
}
void build(int x, int l, int r) {
  int mid = (l + r) / 2, lc = x * 2, rc = x * 2 + 1;
  t[x].l = l;
  t[x].r = r;
  if (l == r) {
    t[x].sum = a[l];
    t[x].f1 = t[x].f2 = 0;
    return;
  }
  build(lc, l, mid);
  build(rc, mid + 1, r);
  t[x].sum = (t[lc].sum + t[rc].sum) % mod;
  t[x].f1 = t[x].f2 = 0;
}
void pushdown(int x) {
  int l = t[x].l, r = t[x].r;
  int mid = (l + r) / 2, lc = x * 2, rc = x * 2 + 1;
  t[lc].f1 = (t[lc].f1 + t[x].f1) % mod;
  t[lc].f2 = (t[lc].f2 + t[x].f2) % mod;
  t[lc].sum += calc_range(t[x].f1, t[x].f2, mid - l + 1);
  t[lc].sum %= mod;
  t[rc].f1 = (t[rc].f1 + calc(t[x].f1, t[x].f2, mid - l + 2)) % mod;
  t[rc].f2 = (t[rc].f2 + calc(t[x].f1, t[x].f2, mid - l + 3)) % mod;
  t[rc].sum += calc_range(t[x].f1, t[x].f2, r - l + 1) -
               calc_range(t[x].f1, t[x].f2, mid - l + 1);
  t[rc].sum = (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) / 2, lc = x * 2, rc = x * 2 + 1;
  if (l >= ql && r <= qr) {
    t[x].f1 = (t[x].f1 + F[l - ql + 1]) % mod;
    t[x].f2 = (t[x].f2 + F[l - ql + 2]) % mod;
    t[x].sum += calc_range(F[l - ql + 1], F[l - ql + 2], r - l + 1);
    t[x].sum %= 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) / 2, lc = x * 2, rc = x * 2 + 1;
  if (l >= ql && r <= qr) return t[x].sum;
  pushdown(x);
  long long ans_left = 0, ans_right = 0;
  if (ql <= mid) ans_left = query(lc, l, mid, ql, qr);
  if (qr > mid) ans_right = query(rc, mid + 1, r, ql, qr);
  return (ans_left + ans_right) % mod;
}
int main() {
  n = read();
  m = read();
  calc_Fibonacci(n);
  for (int i = (1); i <= (n); i++) a[i] = read();
  build(1, 1, n);
  for (int i = (1); i <= (m); i++) {
    int tag, l, r;
    tag = read();
    l = read();
    r = read();
    if (tag == 1)
      update(1, 1, n, l, r);
    else
      printf("%lld\n", query(1, 1, n, l, r));
  }
  return 0;
}
