#include <bits/stdc++.h>
using namespace std;
long long N, M, nn;
long long a[300002];
long long suma[300002];
long long f[300002];
long long sumf[300002];
struct data {
  long long a, b;
  long long tot;
} seg[1200002];
long long s, e;
bool cross(long long x1, long long y1, long long x2, long long y2) {
  if (y1 < x2 || y2 < x1) return false;
  return true;
}
void add(long long node, long long left, long long right) {
  seg[node].tot += (sumf[min(right, e) - s + 1] - sumf[max(left, s) - s]);
  seg[node].tot %= 1000000009;
  if (s <= left && right <= e) {
    seg[node].a += f[left - s];
    seg[node].b += f[left - s + 1];
    seg[node].a %= 1000000009;
    seg[node].b %= 1000000009;
    return;
  }
  int mid = (left + right) / 2;
  if (cross(s, e, left, mid)) add(node * 2, left, mid);
  if (cross(s, e, mid + 1, right)) add((node * 2) + 1, mid + 1, right);
}
long long ans;
long long x, y;
void sum(long long node, long long left, long long right) {
  if (s <= left && right <= e) {
    ans += seg[node].tot;
    ans %= 1000000009;
    return;
  }
  int mid = (left + right) / 2;
  seg[node * 2].a += seg[node].a;
  seg[node * 2].b += seg[node].b;
  seg[node * 2].a %= 1000000009;
  seg[node * 2].b %= 1000000009;
  x = seg[node].a;
  y = seg[node].b;
  seg[node * 2].tot += ((x * sumf[mid - left]) + (y * sumf[mid - left + 1]));
  seg[node * 2].tot %= 1000000009;
  seg[(node * 2) + 1].tot +=
      ((x * sumf[right - left]) + (y * sumf[right - left + 1]));
  seg[(node * 2) + 1].tot -=
      ((seg[node].a * sumf[mid - left]) + (seg[node].b * sumf[mid - left + 1]));
  seg[(node * 2) + 1].tot %= 1000000009;
  x = ((seg[node].a * f[mid - left]) + (seg[node].b * f[mid - left + 1]));
  y = ((seg[node].a * f[mid - left + 1]) + (seg[node].b * f[mid - left + 2]));
  seg[(node * 2) + 1].a += x;
  seg[(node * 2) + 1].b += y;
  seg[(node * 2) + 1].a %= 1000000009;
  seg[(node * 2) + 1].b %= 1000000009;
  seg[node].a = seg[node].b = 0;
  if (cross(s, e, left, mid)) sum(node * 2, left, mid);
  if (cross(s, e, mid + 1, right)) sum((node * 2) + 1, mid + 1, right);
}
long long tmp[300002], ans2;
void process() {
  long long i, j;
  long long op, l, r;
  for (nn = 1; nn < N; nn *= 2)
    ;
  for (i = 1; i <= N; i++) {
    suma[i] = suma[i - 1] + a[i];
    suma[i] %= 1000000009;
  }
  f[1] = f[2] = 1;
  for (i = 3; i <= N; i++) {
    f[i] = f[i - 1] + f[i - 2];
    f[i] %= 1000000009;
  }
  for (i = 1; i <= N; i++) {
    sumf[i] = sumf[i - 1] + f[i];
    sumf[i] %= 1000000009;
    tmp[i] = a[i];
  }
  for (i = 1; i <= M; i++) {
    scanf("%lld %lld %lld", &op, &l, &r);
    if (op == 1) {
      s = l;
      e = r;
      add(1, 1, nn);
    } else {
      s = l;
      e = r;
      ans = 0;
      sum(1, 1, nn);
      ans += suma[e];
      ans -= suma[s - 1];
      ans %= 1000000009;
      if (ans < 0) ans += 1000000009;
      printf("%lld\n", ans);
      ans2 = 0;
    }
  }
}
void clean() {
  long long i;
  for (i = 1; i <= nn * 2; i++) seg[i].a = seg[i].b = seg[i].tot;
}
int main(void) {
  long long i;
  scanf("%lld %lld", &N, &M);
  for (i = 1; i <= N; i++) scanf("%lld", &a[i]);
  process();
  clean();
  return 0;
}
