#include <bits/stdc++.h>
using namespace std;
struct point {
  int x, y;
  point() {}
  point(int a, int b) { x = a, y = b; }
};
template <class T>
T sqr(T a) {
  return a * a;
}
template <class T>
T power(T n, T p) {
  T res = 1;
  for (int i = 0; i < p; i++) res *= n;
  return res;
}
template <class T>
double getdist(T a, T b) {
  return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
template <class T>
T extract(string s, T ret) {
  stringstream ss(s);
  ss >> ret;
  return ret;
}
template <class T>
string tostring(T n) {
  stringstream ss;
  ss << n;
  return ss.str();
}
long long mod = 1000000009;
long long arr[300010], F[300010];
namespace fibonacci {
void gen(int n) {
  F[1] = F[2] = 1;
  for (int i = 3; i <= n; i++) F[i] = (F[i - 1] + F[i - 2]) % mod;
}
long long kth_fibo(long long f1, long long f2, long long k) {
  if (k == 1) return f1;
  if (k == 2) return f2;
  long long ret = (F[k - 1] * f2) % mod;
  ret += (F[k - 2] * f1) % mod;
  ret %= mod;
  return ret;
}
long long sum(long long f1, long long f2, long long k) {
  long long ret = (kth_fibo(f1, f2, k + 2) - f2) % mod;
  ret += mod;
  return ret % mod;
}
}  // namespace fibonacci
struct node {
  long long f1, f2, sum;
  node(long long sum = 0, long long f1 = 0, long long f2 = 0)
      : sum(sum), f1(f1), f2(f2){};
  void add(long long _f1, long long _f2, long long k) {
    f1 += _f1;
    f2 += _f2;
    f1 %= mod;
    f2 %= mod;
    sum += fibonacci::sum(_f1, _f2, k);
    sum %= mod;
  }
};
node segtree[300010 * 4];
void build(int l, int r, int cur) {
  if (l == r) {
    segtree[cur] = node(arr[l] % mod);
    return;
  }
  int lchild = cur << 1, rchild = lchild | 1, m = (l + r) >> 1;
  build(l, m, lchild);
  build(m + 1, r, rchild);
  segtree[cur].sum = segtree[lchild].sum + segtree[rchild].sum;
  segtree[cur].sum %= mod;
}
void push_down(int l, int r, int cur) {
  if (segtree[cur].f1 == 0 && segtree[cur].f2 == 0) return;
  if (l == r) return;
  int lchild = cur << 1, rchild = lchild | 1, m = (l + r) >> 1;
  long long f1, f2, nf1, nf2;
  f1 = segtree[cur].f1;
  f2 = segtree[cur].f2;
  segtree[lchild].add(f1, f2, m - l + 1);
  nf1 = fibonacci::kth_fibo(f1, f2, max(1, m - l + 2));
  nf2 = fibonacci::kth_fibo(f1, f2, max(2, m - l + 3));
  segtree[rchild].add(nf1, nf2, r - m);
  segtree[cur].sum = segtree[lchild].sum + segtree[rchild].sum;
  segtree[cur].sum %= mod;
  segtree[cur].f1 = segtree[cur].f2 = 0;
}
void update(int L, int R, int l, int r, int cur) {
  push_down(l, r, cur);
  if (l > R || r < L) return;
  if (l >= L && r <= R) {
    long long f1 = F[l - L + 1];
    long long f2 = F[l - L + 2];
    segtree[cur].add(f1, f2, r - l + 1);
    return;
  }
  int lchild = cur << 1, rchild = lchild | 1, m = (l + r) >> 1;
  update(L, R, l, m, lchild);
  update(L, R, m + 1, r, rchild);
  segtree[cur].sum = segtree[lchild].sum + segtree[rchild].sum;
  segtree[cur].sum %= mod;
}
long long query(int L, int R, int l, int r, int cur) {
  push_down(l, r, cur);
  if (l > R || r < L) return 0;
  if (l >= L && r <= R) return segtree[cur].sum;
  int lchild = cur << 1, rchild = lchild | 1, m = (l + r) >> 1;
  return (query(L, R, l, m, lchild) + query(L, R, m + 1, r, rchild)) % mod;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, m, i, q, l, r;
  cin >> n >> m;
  for (i = 1; i <= n; i++) cin >> arr[i];
  fibonacci::gen(n);
  build(1, n, 1);
  while (m--) {
    cin >> q >> l >> r;
    if (q == 1)
      update(l, r, 1, n, 1);
    else
      cout << query(l, r, 1, n, 1) << "\n";
  }
  return 0;
}
