#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10, mod = 1e9 + 9;
long long lz[N << 2][2], v[N << 2], a[N], f[N], qz[N];
void Mul(long long &x, long long y) { x = (x * y) % mod; }
long long mul(long long x, long long y) { return x * y % mod; }
void Add(long long &x, long long y) { x = (x + y) % mod; }
long long add(long long x, long long y) { return (x + y) % mod; }
void build(int x, int l, int r) {
  if (l == r) {
    v[x] = a[l];
    return;
  }
  int mid = (l + r) >> 1;
  build(x << 1, l, mid), build(x << 1 | 1, mid + 1, r);
  v[x] = add(v[x << 1], v[x << 1 | 1]);
}
long long js(long long A, long long B, long long nm) {
  if (nm == 1) return A;
  return add(mul(A, add(qz[nm - 2], 1)), mul(qz[nm - 1], B));
}
long long get(long long A, long long B, long long nm) {
  if (nm == 1) return A;
  return add(mul(f[nm - 1], B), mul(f[nm - 2], A));
}
void Get(int x, int l, int r, int L, int R) {
  Add(lz[x][0], f[l - L + 1]);
  if (l + 1 <= r) Add(lz[x][1], f[l - L + 2]);
}
void pushdown(int x, int l, int r) {
  int mid = (l + r) >> 1;
  if (!lz[x][0] && !lz[x][1]) return;
  Add(v[x], js(lz[x][0], lz[x][1], r - l + 1));
  if (l == r) {
    lz[x][0] = lz[x][1] = 0;
    return;
  }
  Add(lz[x << 1][0], lz[x][0]);
  if (mid > l) Add(lz[x << 1][1], lz[x][1]);
  Add(lz[x << 1 | 1][0], get(lz[x][0], lz[x][1], mid + 2 - l));
  if (mid + 1 < r) Add(lz[x << 1 | 1][1], get(lz[x][0], lz[x][1], mid + 3 - l));
  lz[x][0] = lz[x][1] = 0;
}
void change(int x, int l, int r, int L, int R) {
  if (L <= l && r <= R) {
    Get(x, l, r, L, R);
    pushdown(x, l, r);
    return;
  }
  int mid = (l + r) >> 1;
  pushdown(x, l, r);
  if (L <= mid) change(x << 1, l, mid, L, R);
  if (R > mid) change(x << 1 | 1, mid + 1, r, L, R);
  pushdown(x << 1, l, mid), pushdown(x << 1 | 1, mid + 1, r);
  v[x] = add(v[x << 1], v[x << 1 | 1]);
}
long long find(int x, int l, int r, int L, int R) {
  if (L > r || R < l) return 0LL;
  pushdown(x, l, r);
  if (L <= l && r <= R) return v[x];
  int mid = (l + r) >> 1;
  return add(find(x << 1, l, mid, L, R), find(x << 1 | 1, mid + 1, r, L, R));
}
void de(int x, int l, int r) {
  printf("x=%d l=%d r=%d v=%lld lz=%lld,%lld\n", x, l, r, v[x], lz[x][0],
         lz[x][1]);
  if (l == r) return;
  int mid = (l + r) >> 1;
  de(x << 1, l, mid), de(x << 1 | 1, mid + 1, r);
}
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]);
  build(1, 1, n);
  f[1] = 1, f[2] = 1;
  for (int i = 3; i <= n; ++i) f[i] = add(f[i - 1], f[i - 2]);
  for (int i = 1; i <= n; ++i) qz[i] = add(qz[i - 1], f[i]);
  for (int i = 1; i <= m; ++i) {
    int x, y, z;
    scanf("%d%d%d", &x, &y, &z);
    if (x == 1)
      change(1, 1, n, y, z);
    else
      printf("%lld\n", find(1, 1, n, y, z));
  }
  return 0;
}
