#include <bits/stdc++.h>
using namespace std;
long long powm(long long base, long long exp, long long mod = 1000000009) {
  long long ans = 1;
  while (exp) {
    if (exp & 1) ans = (ans * base) % mod;
    exp >>= 1, base = (base * base) % mod;
  }
  return ans;
}
long long ctl(char x, char an = 'a') { return (long long)(x - an); }
char ltc(long long x, char an = 'a') { return (char)(x + an); }
long long first[300005], pref[300005], pref_fib[300005], a[300005];
long long get_fibo_sum(long long l, long long r) {
  return (pref_fib[r] - (l ? pref_fib[l - 1] : 0) + 1000000009) % 1000000009;
}
long long get_fibo(long long st1, long long st2, long long i) {
  if (i == 0)
    return st1;
  else if (i == 1)
    return st2;
  else {
    long long ret = ((first[i - 1] * st2) % 1000000009 +
                     (first[i - 2] * st1) % 1000000009) %
                    1000000009;
    return ret;
  }
}
long long get_fibo_sum(long long st1, long long st2, long long i) {
  if (i == 0)
    return st1;
  else if (i == 1)
    return (st1 + st2) % 1000000009;
  else {
    long long ans = (st2 * get_fibo_sum(1, i - 1)) % 1000000009;
    ans = (ans + (st1 * get_fibo_sum(0, i - 2)) % 1000000009) % 1000000009;
    ans = (ans + st1) % 1000000009;
    ans = (ans + st2) % 1000000009;
    return ans;
  }
}
const pair<long long, long long> khali = make_pair(0LL, 0LL);
struct lazySegTree {
  long long tree[4 * 300005], x, y, val;
  pair<long long, long long> lazy[4 * 300005];
  void push(long long low, long long high, long long pos) {
    if (lazy[pos] != khali) {
      tree[pos] +=
          get_fibo_sum(lazy[pos].first, lazy[pos].second, (high - low));
      if (low != high) {
        pair<long long, long long> tmp;
        tmp = lazy[pos];
        lazy[2 * pos + 1].first =
            (lazy[2 * pos + 1].first + tmp.first) % 1000000009;
        lazy[2 * pos + 1].second =
            (lazy[2 * pos + 1].second + tmp.second) % 1000000009;
        tmp.first = get_fibo(lazy[pos].first, lazy[pos].second,
                             (low + high) / 2 - low + 1);
        tmp.second = get_fibo(lazy[pos].first, lazy[pos].second,
                              (low + high) / 2 - low + 2);
        lazy[2 * pos + 2].first =
            (lazy[2 * pos + 2].first + tmp.first) % 1000000009;
        lazy[2 * pos + 2].second =
            (lazy[2 * pos + 2].second + tmp.second) % 1000000009;
      }
      lazy[pos] = khali;
    }
  }
  long long query(long long low, long long high, long long pos) {
    push(low, high, pos);
    if (x <= low and y >= high) return tree[pos];
    if (x > high || y < low) return 0;
    long long mid = (high + low) / 2;
    return (query(low, mid, 2 * pos + 1) + query(mid + 1, high, 2 * pos + 2)) %
           1000000009;
  }
  void update(long long low, long long high, long long pos) {
    push(low, high, pos);
    if (x > high || y < low) return;
    if (x <= low and y >= high) {
      lazy[pos].first = first[low - x];
      lazy[pos].second = first[low - x + 1];
      push(low, high, pos);
      return;
    }
    long long mid = (low + high) / 2;
    update(low, mid, 2 * pos + 1), update(mid + 1, high, 2 * pos + 2);
    tree[pos] = (tree[2 * pos + 1] + tree[2 * pos + 2]) % 1000000009;
  }
} lst;
int main() {
  first[0] = 1, first[1] = 1;
  for (long long i = 2; i < 300005; i++)
    first[i] = (first[i - 1] + first[i - 2]) % 1000000009;
  for (long long i = 0; i < 4 * 300005; i++) lst.lazy[i] = khali;
  long long type, l, r, n, q;
  cin >> n >> q;
  for (long long i = 1; i < n + 1; i++) cin >> a[i];
  pref_fib[0] = 1;
  for (long long i = 1; i < 300005; i++)
    pref_fib[i] = (pref_fib[i - 1] + first[i]) % 1000000009;
  pref[1] = a[1];
  for (long long i = 1; i < 300005; i++)
    pref[i] = (pref[i - 1] + a[i]) % 1000000009;
  while (q--) {
    cin >> type >> l >> r;
    lst.x = l, lst.y = r;
    if (type == 1) {
      lst.update(1, n, 0);
    } else {
      long long ans = lst.query(1, n, 0);
      ans = (ans + pref[r]) % 1000000009;
      ans = (ans - pref[l - 1] + 1000000009) % 1000000009;
      cout << ans << '\n';
    }
  }
  return 0;
}
