#include <bits/stdc++.h>
using namespace std;
const int inf = (int)1e9;
const double eps = 1e-9;
const int mod = (int)1e9 + 9;
const int maxn = (int)4e5 + 10;
const int N = 700;
int a[maxn];
int sum[maxn / N + 1];
int first[maxn / N + 1];
int second[maxn / N + 1];
int f[maxn];
void upd(int l, int r) {
  if (l / N == r / N) {
    int id = l / N;
    for (int i = l; i <= r; ++i) {
      a[i] += f[i - l + 1];
      sum[id] += f[i - l + 1];
      if (a[i] >= mod) a[i] -= mod;
      if (sum[id] >= mod) sum[id] -= mod;
    }
    return;
  }
  int l2 = (l / N + 1) * N;
  int lid = l / N;
  int r2 = (r / N) * N;
  int rid = r / N;
  for (int i = l; i < l2; ++i) {
    a[i] += f[i - l + 1];
    sum[lid] += f[i - l + 1];
    if (a[i] >= mod) a[i] -= mod;
    if (sum[lid] >= mod) sum[lid] -= mod;
  }
  for (int i = r2; i <= r; ++i) {
    a[i] += f[i - l + 1];
    sum[rid] += f[i - l + 1];
    if (a[i] >= mod) a[i] -= mod;
    if (sum[rid] >= mod) sum[rid] -= mod;
  }
  for (int i = lid + 1; i < rid; ++i) {
    first[i] += f[i * N - l + 1];
    second[i] += f[i * N - l + 2];
    if (first[i] >= mod) first[i] -= mod;
    if (second[i] >= mod) second[i] -= mod;
    int end = (i + 1) * N - l + 1;
    int start = i * N - l + 1;
    int add = (f[end + 1] + mod - f[start + 1]);
    if (add >= mod) add -= mod;
    sum[i] += add;
    if (sum[i] >= mod) sum[i] -= mod;
  }
}
int get2(int id, int l, int r) {
  int f1 = first[id];
  int f2 = second[id];
  long long res = 0;
  for (int i = id * N; i <= r; ++i) {
    if (i >= l) res += a[i] + f1;
    int f3 = f2 + f1;
    if (f3 >= mod) f3 -= mod;
    f1 = f2;
    f2 = f3;
  }
  return (int)(res % mod);
}
int get(int l, int r) {
  int lid = l / N;
  int rid = r / N;
  if (lid == rid) {
    return get2(lid, l, r);
  }
  int l2 = (lid + 1) * N;
  int r2 = rid * N;
  long long res = get2(lid, l, l2 - 1) + get2(rid, r2, r);
  for (int i = lid + 1; i < rid; ++i) res += sum[i];
  return (int)(res % mod);
}
int main() {
  f[1] = 1;
  f[2] = 1;
  for (int i = 3; i < maxn; ++i) f[i] = (f[i - 1] + f[i - 2]) % mod;
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 0; (i) < (n); ++i) scanf("%d", &a[i]);
  for (int i = 0; (i) < (n); ++i) {
    sum[i / N] += a[i];
    if (sum[i / N] >= mod) sum[i / N] -= mod;
  }
  for (int j = 0; (j) < (m); ++j) {
    int t, l, r;
    scanf("%d%d%d", &t, &l, &r);
    l -= 1, r -= 1;
    if (t == 1) {
      upd(l, r);
    } else
      printf("%d\n", get(l, r));
  }
  return 0;
}
