#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 9;
struct node {
  long long x, y, sum;
} st[1200005];
int n, q, type, L, R, a[300005];
long long f[300005];
void build(int id, int l, int r) {
  if (l == r) {
    st[id].sum = a[l];
    return;
  }
  int mid = l + r >> 1;
  build(id << 1, l, mid);
  build(id << 1 | 1, mid + 1, r);
  st[id].sum = (st[id << 1].sum + st[id << 1 | 1].sum) % mod;
}
void push(int id, int l, int r) {
  if (st[id].x == 0 && st[id].y == 0) return;
  int mid = l + r >> 1, pos = mid - l + 2;
  long long x = st[id].x, y = st[id].y;
  st[id << 1].x = (st[id << 1].x + x) % mod;
  st[id << 1].y = (st[id << 1].y + y) % mod;
  st[id << 1].sum =
      (st[id << 1].sum + x * f[mid - l + 1] + y * (f[mid - l + 2] - 1)) % mod;
  st[id << 1 | 1].x =
      (st[id << 1 | 1].x + x * f[pos - 2] + y * f[pos - 1]) % mod;
  st[id << 1 | 1].y = (st[id << 1 | 1].y + x * f[pos - 1] + y * f[pos]) % mod;
  st[id << 1 | 1].sum =
      (st[id << 1 | 1].sum + x * f[r - l + 1] + y * (f[r - l + 2] - 1) -
       x * f[mid - l + 1] - y * (f[mid - l + 2] - 1) + mod) %
      mod;
  st[id].x = st[id].y = 0;
}
void update(int id, int l, int r, int u, int v) {
  if (l > v or r < u) return;
  if (u <= l && r <= v) {
    st[id].x = (st[id].x + f[l - u + 1]) % mod;
    st[id].y = (st[id].y + f[l - u + 2]) % mod;
    st[id].sum = (st[id].sum + f[l - u + 1] * f[r - l + 1] % mod +
                  f[l - u + 2] * (f[r - l + 2] - 1)) %
                 mod;
    return;
  }
  push(id, l, r);
  int mid = l + r >> 1;
  update(id << 1, l, mid, u, v);
  update(id << 1 | 1, mid + 1, r, u, v);
  st[id].sum = (st[id << 1].sum + st[id << 1 | 1].sum) % mod;
}
long long query(int id, int l, int r, int u, int v) {
  if (l > v or r < u) return 0;
  if (u <= l && r <= v) return st[id].sum;
  push(id, l, r);
  int mid = l + r >> 1;
  return (query(id << 1, l, mid, u, v) + query(id << 1 | 1, mid + 1, r, u, v)) %
         mod;
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> q;
  f[1] = 1;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    if (i > 1) f[i] = (f[i - 1] + f[i - 2]) % mod;
  }
  f[n + 1] = (f[n] + f[n - 1]) % mod;
  build(1, 1, n);
  while (q--) {
    cin >> type >> L >> R;
    if (type == 1)
      update(1, 1, n, L, R);
    else
      cout << (query(1, 1, n, L, R) + mod) % mod << endl;
  }
}
