#include <bits/stdc++.h>
using namespace std;
template <typename T, typename V>
inline void bugp(const pair<T, V> &x) {
  if (false) cerr << '{' << x.first << ", " << x.second << "}\n";
}
template <typename T, typename U, typename V>
inline void bugpp(const pair<T, pair<U, V> > &x) {
  if (false)
    cerr << '{' << x.first << ", {" << x.second.first << ", " << x.second.second
         << "}}\n";
}
const int N = 300003, MOD = 1000000009;
int n, arr[N], f[N];
struct segt {
  pair<int, int> lazy;
  int sum;
} st[N << 2];
inline void mod(int &x) {
  if (x >= MOD) x -= MOD;
}
inline int fibo(int x, int a, int b) {
  return ((long long)a * f[x - 2] + (long long)b * f[x - 1]) % MOD;
}
inline int sumfibo(int x, int a, int b) {
  return (fibo(x + 2, a, b) - b + MOD) % MOD;
}
void build(int x = 1, int l = 1, int r = n) {
  if (l == r)
    st[x].sum = arr[l];
  else {
    int mid = l + r >> 1;
    build(x << 1, l, mid);
    build(x << 1 | 1, mid + 1, r);
    st[x].sum = st[x << 1].sum + st[x << 1 | 1].sum;
    mod(st[x].sum);
  }
}
void propagate(int x, int l, int r) {
  if (st[x].lazy != pair<int, int>(0, 0)) {
    int &a = st[x].lazy.first, &b = st[x].lazy.second, mid = l + r >> 1;
    st[x << 1].lazy.first += a;
    mod(st[x << 1].lazy.first);
    st[x << 1].lazy.second += b;
    mod(st[x << 1].lazy.second);
    st[x << 1].sum += sumfibo(mid - l + 1, a, b);
    mod(st[x << 1].sum);
    int aa = fibo(mid - l + 2, a, b), bb = fibo(mid - l + 3, a, b);
    st[x << 1 | 1].lazy.first += aa;
    mod(st[x << 1 | 1].lazy.first);
    st[x << 1 | 1].lazy.second += bb;
    mod(st[x << 1 | 1].lazy.second);
    st[x << 1 | 1].sum += sumfibo(r - mid, aa, bb);
    mod(st[x << 1 | 1].sum);
    a = b = 0;
  }
}
void update(int u, int v, int x = 1, int l = 1, int r = n) {
  if (u > r || v < l)
    return;
  else if (u <= l && r <= v) {
    st[x].lazy.first += f[l - u + 1];
    mod(st[x].lazy.first);
    st[x].lazy.second += f[l - u + 2];
    mod(st[x].lazy.second);
    st[x].sum += sumfibo(r - l + 1, f[l - u + 1], f[l - u + 2]);
    mod(st[x].sum);
    if (false)
      cerr << ("sumfibo(r - l + 1, f[l - u + 1], f[l - u + 2])") << " = "
           << (sumfibo(r - l + 1, f[l - u + 1], f[l - u + 2])) << '\n';
    if (false) cerr << ("x") << " = " << (x) << '\n';
    if (false) cerr << ("l") << " = " << (l) << '\n';
    if (false) cerr << ("r") << " = " << (r) << '\n';
    if (false) cerr << ("st[x].sum") << " = " << (st[x].sum) << '\n';
    return;
  }
  int mid = l + r >> 1;
  propagate(x, l, r);
  update(u, v, x << 1, l, mid);
  update(u, v, x << 1 | 1, mid + 1, r);
  st[x].sum = st[x << 1].sum + st[x << 1 | 1].sum;
  mod(st[x].sum);
}
int getSum(int u, int v, int x = 1, int l = 1, int r = n) {
  if (u > r || v < l)
    return 0;
  else if (u <= l && r <= v)
    return st[x].sum;
  int mid = l + r >> 1, s;
  propagate(x, l, r);
  return (getSum(u, v, x << 1, l, mid) + getSum(u, v, x << 1 | 1, mid + 1, r)) %
         MOD;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int m, l, r, t;
  cin >> n >> m;
  for (int i = 1, _n = (n); i <= _n; ++i) cin >> arr[i];
  f[1] = f[2] = 1;
  for (int i = (3), _b = (n + 2); i <= _b; ++i) {
    f[i] = f[i - 1] + f[i - 2];
    mod(f[i]);
  }
  build();
  if (false) cerr << ("f[4]") << " = " << (f[4]) << '\n';
  if (false) cerr << ("f[5]") << " = " << (f[5]) << '\n';
  if (false) cerr << ("f[6]") << " = " << (f[6]) << '\n';
  while (m--) {
    cin >> t >> l >> r;
    if (t == 1)
      update(l, r);
    else
      cout << getSum(l, r) << '\n';
  }
  return 0;
}
