#include <bits/stdc++.h>
using namespace std;
const int MAXN = 300005;
const long long MODER = 1000000009;
void MOD(long long &a) {
  if (a >= MODER || a < 0) {
    a %= MODER;
    if (a < 0) a += MODER;
  }
}
long long A[300005], B[300005], SA[300005], SB[300005];
void proc(int n) {
  A[1] = 1, A[2] = 0;
  B[1] = 0, B[2] = 1;
  for (int i = 3; i <= n; i++) {
    A[i] = A[i - 2] + A[i - 1];
    MOD(A[i]);
    B[i] = B[i - 2] + B[i - 1];
    MOD(B[i]);
  }
  for (int i = 1; i <= n; i++) {
    SA[i] = SA[i - 1] + A[i];
    SB[i] = SB[i - 1] + B[i];
    MOD(SA[i]), MOD(SB[i]);
  }
}
long long getval(long long a, long long b, long long k) {
  long long ret = a * A[k];
  MOD(ret);
  ret += b * B[k];
  MOD(ret);
  return ret;
}
long long getsum(long long a, long long b, long long k) {
  long long ret = a * SA[k];
  MOD(ret);
  ret += b * SB[k];
  MOD(ret);
  return ret;
}
struct Lazymark {
  long long a, b;
} segLazy[MAXN * 4];
long long segTree[MAXN * 4];
void segTree_pushdown(int cur, int cl, int cr) {
  long long siz = cr - cl + 1;
  if (segLazy[cur].a || segLazy[cur].b) {
    long long mid = (cl + cr) / 2;
    long long lsiz = mid - cl + 1, rsiz = siz - lsiz;
    if (lsiz == 1) {
      segTree[(cur << 1)] += segLazy[cur].a;
      MOD(segTree[(cur << 1)]);
    } else {
      segTree[(cur << 1)] += getsum(segLazy[cur].a, segLazy[cur].b, lsiz);
      segLazy[(cur << 1)].a += segLazy[cur].a;
      segLazy[(cur << 1)].b += segLazy[cur].b;
      MOD(segLazy[(cur << 1)].a), MOD(segLazy[(cur << 1)].b),
          MOD(segTree[(cur << 1)]);
    }
    if (rsiz == 1) {
      segTree[((cur << 1) + 1)] +=
          getval(segLazy[cur].a, segLazy[cur].b, lsiz + 1);
      MOD(segTree[((cur << 1) + 1)]);
    } else {
      segTree[((cur << 1) + 1)] +=
          getsum(getval(segLazy[cur].a, segLazy[cur].b, lsiz + 1),
                 getval(segLazy[cur].a, segLazy[cur].b, lsiz + 2), rsiz);
      segLazy[((cur << 1) + 1)].a +=
          getval(segLazy[cur].a, segLazy[cur].b, lsiz + 1);
      segLazy[((cur << 1) + 1)].b +=
          getval(segLazy[cur].a, segLazy[cur].b, lsiz + 2);
      MOD(segLazy[((cur << 1) + 1)].a), MOD(segLazy[((cur << 1) + 1)].b),
          MOD(segTree[((cur << 1) + 1)]);
    }
    segLazy[cur].a = segLazy[cur].b = 0;
  }
}
void segTree_update(int l, int r, int cur, int cl, int cr) {
  int siz = cr - cl + 1;
  if (cl > r || cr < l) {
    return;
  } else if (cl >= l && cr <= r) {
    if (siz == 1) {
      segTree[cur] += getval(1, 1, cl - l + 1);
      MOD(segTree[cur]);
    } else {
      segLazy[cur].a += getval(1, 1, cl - l + 1);
      segLazy[cur].b += getval(1, 1, cl - l + 2);
      segTree[cur] +=
          getsum(getval(1, 1, cl - l + 1), getval(1, 1, cl - l + 2), siz);
      MOD(segLazy[cur].a), MOD(segLazy[cur].b), MOD(segTree[cur]);
    }
  } else {
    segTree_pushdown(cur, cl, cr);
    segTree_update(l, r, (cur << 1), cl, (cl + cr) / 2);
    segTree_update(l, r, ((cur << 1) + 1), (cl + cr) / 2 + 1, cr);
    if (l <= r) {
      segTree[cur] = segTree[(cur << 1)] + segTree[((cur << 1) + 1)];
    }
    MOD(segTree[cur]);
  }
}
long long segTree_qres;
void segTree_query(int l, int r, int cur, int cl, int cr) {
  int siz = cr - cl + 1;
  if (cl > r || cr < l) {
    return;
  } else if (cl >= l && cr <= r) {
    segTree_qres += segTree[cur];
    MOD(segTree_qres);
  } else {
    segTree_pushdown(cur, cl, cr);
    segTree_query(l, r, (cur << 1), cl, (cl + cr) / 2);
    segTree_query(l, r, ((cur << 1) + 1), (cl + cr) / 2 + 1, cr);
  }
}
long long arr[300005];
int main() {
  int n, m;
  scanf(" %d %d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf(" %I64d", &arr[i]);
    arr[i] += arr[i - 1];
    MOD(arr[i]);
  }
  proc(n);
  for (int i = 1; i <= m; i++) {
    int a, b, c;
    scanf(" %d %d %d", &a, &b, &c);
    if (a == 1) {
      segTree_update(b, c, 1, 1, n);
    } else {
      segTree_qres = 0;
      segTree_query(b, c, 1, 1, n);
      segTree_qres += arr[c] - arr[b - 1];
      MOD(segTree_qres);
      printf("%I64d\n", segTree_qres);
    }
  }
  return 0;
}
