#include <bits/stdc++.h>
long long fib[300010], fs[300010][2], fm[300010][2], A[300010], st[20 * 300010],
    lazy_a[20 * 300010], lazy_b[20 * 300010];
int n, m;
void build(int node, int L, int R) {
  lazy_a[node] = lazy_b[node] = 0;
  if (L == R) {
    st[node] = A[L];
    return;
  }
  build(2 * (node), L, (L + R) / 2);
  build(2 * (node) + 1, (L + R) / 2 + 1, R);
  st[node] = (st[2 * (node)] + st[2 * (node) + 1]) % 1000000009;
}
void relax(int node, int L, int R) {
  if (lazy_a[node] == 0) return;
  if (L != R) {
    lazy_a[2 * (node)] = (lazy_a[2 * (node)] + lazy_a[node]) % 1000000009;
    lazy_b[2 * (node)] = (lazy_b[2 * (node)] + lazy_b[node]) % 1000000009;
    lazy_a[2 * (node) + 1] =
        (lazy_a[2 * (node) + 1] +
         ((fm[(R - L) / 2 + 1][0] * lazy_b[node]) % 1000000009 +
          (fm[(R - L) / 2 + 1][1] * lazy_a[node]) % 1000000009) %
             1000000009) %
        1000000009;
    lazy_b[2 * (node) + 1] =
        (lazy_b[2 * (node) + 1] +
         ((fm[(R - L) / 2 + 2][0] * lazy_b[node]) % 1000000009 +
          (fm[(R - L) / 2 + 2][1] * lazy_a[node]) % 1000000009) %
             1000000009) %
        1000000009;
  }
  st[node] = (st[node] + ((fs[R - L][0] * lazy_b[node]) % 1000000009 +
                          (fs[R - L][1] * lazy_a[node]) % 1000000009) %
                             1000000009) %
             1000000009;
  lazy_a[node] = lazy_b[node] = 0;
}
long long query(int node, int qL, int qR, int L, int R) {
  relax(node, L, R);
  if (R < qL || L > qR) return 0;
  if (L >= qL && R <= qR) {
    return st[node];
  }
  return (query(2 * (node), qL, qR, L, (L + R) / 2) +
          query(2 * (node) + 1, qL, qR, (L + R) / 2 + 1, R)) %
         1000000009;
}
void update(int node, int qL, int qR, int L, int R) {
  relax(node, L, R);
  if (R < qL || L > qR) return;
  if (L == R) {
    st[node] = (st[node] + fib[L - qL]) % 1000000009;
    return;
  }
  if (L >= qL && R <= qR) {
    lazy_a[node] = fib[L - qL];
    lazy_b[node] = fib[L - qL + 1];
    relax(node, L, R);
    return;
  }
  update(2 * (node), qL, qR, L, (L + R) / 2);
  update(2 * (node) + 1, qL, qR, (L + R) / 2 + 1, R);
  st[node] = (st[2 * (node)] + st[2 * (node) + 1]) % 1000000009;
}
std::vector<std::vector<long long> > M(2, std::vector<long long>(2, 1));
inline void mmult(const std::vector<std::vector<long long> > &A,
                  std::vector<std::vector<long long> > &B) {
  B.assign(2, std::vector<long long>(2, 0));
  for (int i = 0; i < 2; i++) {
    for (int j = 0; j < 2; j++) {
      for (int k = 0; k < 2; k++) {
        B[i][j] = (B[i][j] + (A[i][k] * M[k][j]) % 1000000009) % 1000000009;
      }
    }
  }
}
void precalc() {
  fib[0] = fib[1] = 1;
  for (int i = 2; i < 300010; i++) {
    fib[i] = (fib[i - 1] + fib[i - 2]) % 1000000009;
  }
  M[1][1] = 0;
  std::vector<std::vector<long long> > A(2, std::vector<long long>(2, 0)), m_n;
  A[0][0] = A[1][1] = 1;
  fs[0][0] = fm[0][0] = 0;
  fs[0][1] = fm[0][1] = 1;
  for (int i = 1; i < 300010; i++) {
    mmult(A, m_n);
    A = m_n;
    fm[i][0] = A[1][0];
    fm[i][1] = A[1][1];
    fs[i][0] = fs[i - 1][0] + A[1][0];
    if (fs[i][0] > 1000000009) fs[i][0] %= 1000000009;
    fs[i][1] = fs[i - 1][1] + A[1][1];
    if (fs[i][1] > 1000000009) fs[i][1] %= 1000000009;
  }
}
int main() {
  precalc();
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++) {
    scanf("%d", &A[i]);
  }
  build(1, 0, n - 1);
  int t, l, r;
  for (int i = 0; i < m; i++) {
    scanf("%d%d%d", &t, &l, &r);
    if (t == 1) {
      update(1, l - 1, r - 1, 0, n - 1);
    } else if (t == 2) {
      long long ans = query(1, l - 1, r - 1, 0, n - 1);
      if (ans < 0) {
        ans += 1000000009;
      }
      printf("%lld\n", ans);
    }
  }
}
