#include <bits/stdc++.h>
const int P = 1e9 + 9, N = 3e5 + 10;
long long fba[N], fbb[N], sma[N], smb[N];
struct {
  int l, r;
  long long sum, taga, tagb;
} a[N * 4];
void build_tree(int p, int l, int r) {
  a[p].l = l;
  a[p].r = r;
  if (l == r)
    scanf("%lld", &a[p].sum);
  else {
    int mid = (l + r) / 2;
    build_tree(p * 2, l, mid);
    build_tree(p * 2 + 1, mid + 1, r);
    a[p].sum = (a[p * 2].sum + a[p * 2 + 1].sum) % P;
  }
}
void push_down(int p) {
  int mid = (a[p].l + a[p].r) / 2;
  (a[p * 2].taga += a[p].taga) %= P;
  (a[p * 2].tagb += a[p].tagb) %= P;
  (a[p * 2].sum +=
   a[p].taga * sma[mid - a[p].l + 1] + a[p].tagb * smb[mid - a[p].l + 1]) %= P;
  long long tga = (fba[mid - a[p].l + 2] * a[p].taga +
                   fbb[mid - a[p].l + 2] * a[p].tagb) %
                  P,
            tgb = (fba[mid - a[p].l + 3] * a[p].taga +
                   fbb[mid - a[p].l + 3] * a[p].tagb) %
                  P;
  (a[p * 2 + 1].taga += tga) %= P;
  (a[p * 2 + 1].tagb += tgb) %= P;
  (a[p * 2 + 1].sum += tga * sma[a[p].r - mid] + tgb * smb[a[p].r - mid]) %= P;
  a[p].taga = a[p].tagb = 0;
}
void add(int p, int l, int r, long long tga, long long tgb) {
  if (a[p].l == l && a[p].r == r) {
    a[p].taga += tga;
    a[p].tagb += tgb;
    (a[p].sum += sma[r - l + 1] * tga + smb[r - l + 1] * tgb) %= P;
    return;
  }
  push_down(p);
  int mid = (a[p].l + a[p].r) / 2;
  if (r <= mid)
    add(p * 2, l, r, tga, tgb);
  else if (l > mid)
    add(p * 2 + 1, l, r, tga, tgb);
  else {
    add(p * 2, l, mid, tga, tgb);
    add(p * 2 + 1, mid + 1, r,
        (tga * fba[mid - l + 2] + tgb * fbb[mid - l + 2]) % P,
        (tga * fba[mid - l + 3] + tgb * fbb[mid - l + 3]) % P);
  }
  a[p].sum = (a[p * 2].sum + a[p * 2 + 1].sum) % P;
}
long long query(int p, int l, int r) {
  if (a[p].l == l && a[p].r == r) return a[p].sum;
  push_down(p);
  int mid = (a[p].l + a[p].r) / 2;
  if (r <= mid)
    return query(p * 2, l, r);
  else if (l > mid)
    return query(p * 2 + 1, l, r);
  else
    return (query(p * 2, l, mid) + query(p * 2 + 1, mid + 1, r)) % P;
}
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  fba[1] = fbb[2] = 1;
  for (int i = 3; i <= N - 1; ++i) {
    fba[i] = (fba[i - 1] + fba[i - 2]) % P;
    fbb[i] = (fbb[i - 1] + fbb[i - 2]) % P;
  }
  for (int i = 1; i <= N - 1; ++i) {
    sma[i] = (sma[i - 1] + fba[i]) % P;
    smb[i] = (smb[i - 1] + fbb[i]) % P;
  }
  build_tree(1, 1, n);
  for (int i = 1; i <= m; ++i) {
    int t, l, r;
    scanf("%d%d%d", &t, &l, &r);
    if (t == 1)
      add(1, l, r, 1, 1);
    else
      printf("%lld\n", query(1, l, r));
  }
  return 0;
}
