#include <bits/stdc++.h>
using namespace std;
long long n, q, ar[300005], fib[300005], seg[1600005];
pair<long long, long long> lazy[1600005];
inline long long fibval(long long x, long long y, long long k) {
  if (k == 1) return x;
  if (k == 2) return y;
  return ((y * fib[k - 1]) % 1000000009 + (x * fib[k - 2]) % 1000000009) %
         1000000009;
}
inline long long upd(long long v, long long l, long long r,
                     pair<long long, long long> val) {
  long long x = val.first, y = val.second, wid = r - l + 1;
  seg[v] = (seg[v] + fibval(x, y, wid + 2) - y + 1000000009) % 1000000009;
  lazy[v] = make_pair((lazy[v].first + x) % 1000000009,
                      (lazy[v].second + y) % 1000000009);
}
inline long long prop(long long v, long long l, long long r) {
  long long idx = (l + r) / 2 + 1;
  upd(2 * v, l, (l + r) / 2, lazy[v]);
  upd(2 * v + 1, (l + r) / 2 + 1, r,
      make_pair(fibval(lazy[v].first, lazy[v].second, (idx - l + 1)),
                fibval(lazy[v].first, lazy[v].second, (idx - l + 2))));
  lazy[v] = make_pair(0, 0);
}
void init(long long v = 1, long long l = 1, long long r = n) {
  if (l == r) {
    seg[v] = ar[l];
    return;
  }
  init(2 * v, l, (l + r) / 2);
  init(2 * v + 1, (l + r) / 2 + 1, r);
  seg[v] = (seg[2 * v] + seg[2 * v + 1]) % 1000000009;
}
void update(long long l, long long r, long long v = 1, long long a = 1,
            long long b = n) {
  if (l <= a && b <= r) {
    upd(v, a, b, make_pair(fib[a - l + 1], fib[a - l + 2]));
    return;
  }
  prop(v, a, b);
  if (r <= (a + b) / 2)
    update(l, r, 2 * v, a, (a + b) / 2);
  else if (l > (a + b) / 2)
    update(l, r, 2 * v + 1, (a + b) / 2 + 1, b);
  else {
    update(l, r, 2 * v, a, (a + b) / 2);
    update(l, r, 2 * v + 1, (a + b) / 2 + 1, b);
  }
  seg[v] = (seg[2 * v] + seg[2 * v + 1]) % 1000000009;
  return;
}
long long query(long long l, long long r, long long v = 1, long long a = 1,
                long long b = n) {
  if (l <= a && b <= r) return seg[v];
  prop(v, a, b);
  if (r <= (a + b) / 2) return query(l, r, 2 * v, a, (a + b) / 2);
  if (l > (a + b) / 2) return query(l, r, 2 * v + 1, (a + b) / 2 + 1, b);
  return (query(l, r, 2 * v, a, (a + b) / 2) +
          query(l, r, 2 * v + 1, (a + b) / 2 + 1, b)) %
         1000000009;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> q;
  for (long long i = 1; i <= n; ++i) cin >> ar[i];
  fib[1] = fib[2] = 1;
  for (long long i = 3; i <= 300002; ++i)
    fib[i] = (fib[i - 1] + fib[i - 2]) % 1000000009;
  init();
  while (q--) {
    long long ty, l, r;
    cin >> ty >> l >> r;
    if (ty == 1)
      update(l, r);
    else
      cout << query(l, r) << "\n";
  }
}
