#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10;
const long long MOD = 1e9 + 9;
struct Mat {
  long long a[3][3];
  Mat() { memset(a, 0, sizeof(a)); }
  Mat operator*(const Mat& tmp) const {
    Mat ans;
    for (int i = 0; i < 3; i++) {
      for (int j = 0; j < 3; j++) {
        for (int k = 0; k < 3; k++) {
          (ans.a[i][j] += a[i][k] * tmp.a[k][j]) %= MOD;
        }
      }
    }
    return ans;
  }
};
long long f[N << 2][2], val[N << 2];
long long a[N];
long long fib[N];
Mat pw[N];
long long cals(long long x[2], int n) {
  if (n == 0)
    return 0;
  else if (n == 1)
    return x[0];
  else if (n == 2)
    return (x[0] + x[1]) % MOD;
  long long t[3] = {x[0] + x[1], x[0], x[1]};
  long long ans = 0;
  for (int i = 0; i < 3; i++) {
    (ans += t[i] * pw[n - 2].a[i][0]) %= MOD;
  }
  return ans;
}
long long cal(long long x[2], int a, int b, int l, int r) {
  a = a - l + 1, b = b - l + 1;
  return (cals(x, b) - cals(x, a - 1)) % MOD;
}
void init() {
  fib[1] = fib[2] = 1;
  for (int i = 3; i < N; i++) fib[i] = (fib[i - 1] + fib[i - 2]) % MOD;
  pw[1].a[0][0] = pw[1].a[1][0] = pw[1].a[2][0] = 1;
  pw[1].a[0][1] = pw[1].a[2][2] = 1;
  for (int i = 2; i < N; i++) pw[i] = pw[i - 1] * pw[1];
}
void update(int root, int l, int r, int a, int b, int c) {
  if (l == a && r == b) {
    (f[root][0] += fib[c]) %= MOD;
    (f[root][1] += fib[c + 1]) %= MOD;
    val[root] =
        cal(f[root], l, r, l, r) + val[(root << 1)] + val[(root << 1 | 1)];
    val[root] %= MOD;
    return;
  }
  int m = (l + r) >> 1;
  if (b <= m)
    update((root << 1), l, m, a, b, c);
  else if (a > m)
    update((root << 1 | 1), m + 1, r, a, b, c);
  else {
    update((root << 1), l, m, a, m, c);
    update((root << 1 | 1), m + 1, r, m + 1, b, c + m - a + 1);
  }
  val[root] =
      cal(f[root], l, r, l, r) + val[(root << 1)] + val[(root << 1 | 1)];
  val[root] %= MOD;
}
long long query(int root, int l, int r, int a, int b) {
  if (l == a && r == b) return val[root];
  long long ans = cal(f[root], a, b, l, r);
  int m = (l + r) >> 1;
  if (b <= m)
    ans += query((root << 1), l, m, a, b);
  else if (a > m)
    ans += query((root << 1 | 1), m + 1, r, a, b);
  else {
    ans += query((root << 1), l, m, a, m) +
           query((root << 1 | 1), m + 1, r, m + 1, b);
  }
  return ans % MOD;
}
void solve() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%lld", a + i);
    (a[i] += a[i - 1]) %= MOD;
  }
  while (m--) {
    int t, l, r;
    scanf("%d%d%d", &t, &l, &r);
    if (t == 1) {
      update(1, 1, n, l, r, 1);
    } else {
      long long ans = query(1, 1, n, l, r);
      ans += a[r] - a[l - 1];
      ans %= MOD;
      (ans += MOD) %= MOD;
      printf("%lld\n", ans);
    }
  }
}
int main() {
  init();
  solve();
  return 0;
}
