#include <bits/stdc++.h>
using namespace std;
struct xint {
  int l, r;
  long long f1, f2, sum;
} tree[1200000];
int n, m;
long long a[300010], f[400000];
long long calcf(long long fx, long long fy, int x) {
  if (x == 1) return fx;
  if (x == 2) return fy;
  return (fx * f[x - 2] + fy * f[x - 1]) % 1000000009;
}
long long calcs(long long fx, long long fy, int x) {
  return (calcf(fx, fy, x + 2) - fy + 1000000009) % 1000000009;
}
void build(int l, int r, int k) {
  tree[k].l = l, tree[k].r = r;
  tree[k].f1 = tree[k].f2 = 0;
  if (l == r) {
    tree[k].sum = a[l];
    return;
  }
  int mid = (l + r) / 2;
  build(l, mid, k * 2);
  build(mid + 1, r, k * 2 + 1);
  tree[k].sum = (tree[k * 2].sum + tree[k * 2 + 1].sum) % 1000000009;
}
void pushdown(int x) {
  if (tree[x].f1) {
    int i = x * 2, j = x * 2 + 1, mid = (tree[x].l + tree[x].r) / 2;
    int fx = calcf(tree[x].f1, tree[x].f2, mid - tree[x].l + 2);
    int fy = calcf(tree[x].f1, tree[x].f2, mid - tree[x].l + 3);
    tree[i].f1 = (tree[i].f1 + tree[x].f1) % 1000000009;
    tree[i].f2 = (tree[i].f2 + tree[x].f2) % 1000000009;
    tree[j].f1 = (tree[j].f1 + fx) % 1000000009;
    tree[j].f2 = (tree[j].f2 + fy) % 1000000009;
    tree[i].sum =
        (tree[i].sum + calcs(tree[x].f1, tree[x].f2, mid - tree[x].l + 1)) %
        1000000009;
    tree[j].sum = (tree[j].sum + calcs(fx, fy, tree[x].r - mid)) % 1000000009;
    tree[x].f1 = tree[x].f2 = 0;
  }
}
void update(int k, int l, int r) {
  if (l <= tree[k].l && tree[k].r <= r) {
    tree[k].f1 = (tree[k].f1 + f[tree[k].l - l + 1]) % 1000000009;
    tree[k].f2 = (tree[k].f2 + f[tree[k].l - l + 2]) % 1000000009;
    tree[k].sum =
        (tree[k].sum + calcs(f[tree[k].l - l + 1], f[tree[k].l - l + 2],
                             tree[k].r - tree[k].l + 1)) %
        1000000009;
    return;
  }
  pushdown(k);
  int mid = (tree[k].l + tree[k].r) / 2;
  if (l <= mid) update(k * 2, l, r);
  if (r > mid) update(k * 2 + 1, l, r);
  tree[k].sum = (tree[k * 2].sum + tree[k * 2 + 1].sum) % 1000000009;
}
long long query(int k, int l, int r) {
  if (l <= tree[k].l && tree[k].r <= r) {
    return tree[k].sum;
  }
  long long ans = 0;
  pushdown(k);
  int mid = (tree[k].l + tree[k].r) / 2;
  if (l <= mid) ans += query(2 * k, l, r);
  if (r > mid) ans += query(2 * k + 1, l, r);
  return ans % 1000000009;
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]);
  f[1] = 1, f[2] = 1;
  for (int i = 3; i <= n + 5; ++i) f[i] = (f[i - 1] + f[i - 2]) % 1000000009;
  build(1, n, 1);
  for (int i = 1; i <= m; ++i) {
    int tmp, l, r;
    scanf("%d%d%d", &tmp, &l, &r);
    if (tmp == 1)
      update(1, l, r);
    else
      printf("%lld\n", query(1, l, r));
  }
  return 0;
}
