#include <bits/stdc++.h>
using namespace std;
const int N = 300100;
const int mod = 1000000009;
long long sum[N << 2];
long long f[N];
long long fa[N << 2], fb[N << 2];
void pre(int n) {
  f[1] = f[2] = 1;
  for (int i = 3; i <= n + 10; i++) f[i] = (f[i - 1] + f[i - 2]) % mod;
}
long long getFB(long long a, long long b, int n) {
  if (n == 1) return a;
  if (n == 2) return b;
  return (b * f[n - 1] + a * f[n - 2]) % mod;
}
void build(int l, int r, int i) {
  fa[i] = fb[i] = 0;
  if (l == r) {
    scanf("%I64d", &sum[i]);
    return;
  }
  int mid = (l + r) >> 1;
  build(l, mid, i << 1);
  build(mid + 1, r, i << 1 | 1);
  sum[i] = (sum[i << 1] + sum[i << 1 | 1]) % mod;
}
void pushDown(int l, int r, int i) {
  if (fa[i] || fb[i]) {
    int mid = (l + r) >> 1;
    fa[i << 1] = (fa[i << 1] + fa[i]) % mod;
    fb[i << 1] = (fb[i << 1] + fb[i]) % mod;
    fa[i << 1 | 1] =
        (fa[i << 1 | 1] + getFB(fa[i], fb[i], mid + 1 - l + 1)) % mod;
    fb[i << 1 | 1] =
        (fb[i << 1 | 1] + getFB(fa[i], fb[i], mid + 2 - l + 1)) % mod;
    long long lsum = (getFB(fa[i], fb[i], mid - l + 1 + 2) - fb[i] + mod) % mod;
    long long rsum =
        (getFB(fa[i], fb[i], r - l + 1 + 2) - fb[i] - lsum + mod) % mod;
    sum[i << 1] = (sum[i << 1] + lsum) % mod;
    sum[i << 1 | 1] = (sum[i << 1 | 1] + rsum) % mod;
    fa[i] = fb[i] = 0;
  }
}
void update(int L, int R, int l, int r, int i) {
  if (L <= l && R >= r) {
    fa[i] = (fa[i] + f[l - L + 1]) % mod;
    fb[i] = (fb[i] + f[l - L + 2]) % mod;
    sum[i] = (sum[i] + getFB(f[l - L + 1], f[l - L + 2], r - l + 1 + 2) -
              f[l - L + 2] + mod) %
             mod;
    return;
  }
  pushDown(l, r, i);
  int mid = (l + r) >> 1;
  if (L <= mid) update(L, R, l, mid, i << 1);
  if (R > mid) update(L, R, mid + 1, r, i << 1 | 1);
  sum[i] = (sum[i << 1] + sum[i << 1 | 1]) % mod;
}
long long query(int L, int R, int l, int r, int i) {
  if (L <= l && R >= r) return sum[i];
  pushDown(l, r, i);
  int mid = (l + r) >> 1;
  long long ret = 0;
  if (L <= mid) ret += query(L, R, l, mid, i << 1);
  if (R > mid) ret += query(L, R, mid + 1, r, i << 1 | 1);
  return ret % mod;
}
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  int a, b, c;
  pre(n);
  build(1, n, 1);
  while (m--) {
    scanf("%d%d%d", &c, &a, &b);
    if (c == 1)
      update(a, b, 1, n, 1);
    else
      printf("%I64d\n", (query(a, b, 1, n, 1) + mod) % mod);
  }
  return 0;
}
