#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
const int N = 300009;
const int inf = 0x3f3f3f3f;
const long long oo = 0x3f3f3f3f3f3f3f3fll;
const int mod = 1e9 + 9;
pair<long long, long long> f[N];
long long sum[N];
int a[N];
struct Seg {
  int l, r;
  long long f1, f2;
  long long sum;
} tree[N * 4];
void PushDown(int idx) {
  int lsz = tree[idx << 1].r - tree[idx << 1].l + 1;
  int rsz = tree[idx << 1 | 1].r - tree[idx << 1 | 1].l + 1;
  long long &f1 = tree[idx].f1;
  long long &f2 = tree[idx].f2;
  tree[idx << 1].f1 = (tree[idx << 1].f1 + f1) % mod;
  tree[idx << 1].f2 = (tree[idx << 1].f2 + f2) % mod;
  tree[idx << 1].sum +=
      f1 * sum[lsz] % mod + f2 * sum[lsz + 1] % mod - f2 + mod;
  tree[idx << 1].sum %= mod;
  tree[idx << 1 | 1].f1 = (tree[idx << 1 | 1].f1 + f1 * f[lsz + 1].first % mod +
                           f2 * f[lsz + 2].first % mod) %
                          mod;
  tree[idx << 1 | 1].f2 =
      (tree[idx << 1 | 1].f2 + f1 * f[lsz + 1].second % mod +
       f2 * f[lsz + 2].second % mod) %
      mod;
  tree[idx << 1 | 1].sum += f1 * (sum[lsz + rsz] - sum[lsz] + mod) % mod +
                            f2 * (sum[lsz + rsz + 1] - sum[lsz + 1]) % mod +
                            mod;
  tree[idx << 1 | 1].sum %= mod;
  f1 = f2 = 0;
  return;
}
void BTree(int l, int r, int idx) {
  tree[idx].l = l;
  tree[idx].r = r;
  tree[idx].f1 = 0;
  tree[idx].f2 = 0;
  tree[idx].sum = a[l];
  if (l == r) return;
  int mid = (l + r) >> 1;
  BTree(l, mid, idx << 1);
  BTree(mid + 1, r, idx << 1 | 1);
  tree[idx].sum = (tree[idx << 1].sum + tree[idx << 1 | 1].sum) % mod;
}
void insert(int l, int r, long long x, long long y, int idx) {
  if (tree[idx].l == l && tree[idx].r == r) {
    int sz = r - l + 1;
    long long k = sum[sz] * x % mod + sum[sz + 1] * y % mod - y + mod;
    k %= mod;
    (tree[idx].sum += k) %= mod;
    tree[idx].f1 = (tree[idx].f1 + x) % mod;
    tree[idx].f2 = (tree[idx].f2 + y) % mod;
    return;
  }
  PushDown(idx);
  int mid = (tree[idx].l + tree[idx].r) >> 1;
  if (r <= mid)
    insert(l, r, x, y, idx << 1);
  else if (l > mid)
    insert(l, r, x, y, idx << 1 | 1);
  else {
    insert(l, mid, x, y, idx << 1);
    int lsz = mid - l + 1;
    long long tx =
        (f[lsz + 1].first * x % mod + f[lsz + 2].first * y % mod) % mod;
    long long ty =
        (f[lsz + 1].second * x % mod + f[lsz + 2].second * y % mod) % mod;
    insert(mid + 1, r, tx, ty, idx << 1 | 1);
  }
  tree[idx].sum = (tree[idx << 1].sum + tree[idx << 1 | 1].sum) % mod;
}
long long query(int l, int r, int idx) {
  if (tree[idx].l == l && tree[idx].r == r) {
    return tree[idx].sum;
  }
  PushDown(idx);
  int mid = (tree[idx].l + tree[idx].r) >> 1;
  long long ret = 0;
  if (r <= mid)
    ret += query(l, r, idx << 1);
  else if (l > mid)
    ret += query(l, r, idx << 1 | 1);
  else
    ret += query(l, mid, idx << 1), ret += query(mid + 1, r, idx << 1 | 1);
  ret %= mod;
  tree[idx].sum = (tree[idx << 1].sum + tree[idx << 1 | 1].sum) % mod;
  return ret;
}
int main() {
  f[1] = make_pair(1, 0);
  f[2] = make_pair(0, 1);
  for (int i = 3; i < N; i++)
    f[i] = make_pair((f[i - 1].first + f[i - 2].first) % mod,
                     (f[i - 1].second + f[i - 2].second) % mod);
  sum[1] = 1;
  for (int i = 2; i < N; i++)
    sum[i] = (sum[i - 1] + f[i].first + f[i].second) % mod;
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  BTree(1, n, 1);
  for (int i = 0; i < m; i++) {
    int t, l, r;
    scanf("%d%d%d", &t, &l, &r);
    if (t == 1) {
      insert(l, r, 1, 0, 1);
    } else {
      cout << query(l, r, 1) << endl;
    }
  }
  return 0;
}
