#include <bits/stdc++.h>
using namespace std;
const int maxn = 3000 * 100 + 100, maxQ = 600, mod = 1000 * 1000 * 1000 + 9;
int n, first[maxn], sum[maxQ], fi[maxQ], se[maxQ], A[maxn], dp[maxn];
vector<pair<int, int> > part;
void decom() {
  int st = 0, Q = sqrt(n), id = 0;
  while (st < n) {
    part.push_back(pair<int, int>(st, min(st + Q, n)));
    for (int j = st; j < st + Q; j++) sum[id] += A[j], sum[id] %= mod;
    id++;
    st += Q;
  }
}
void add(int a, int b) {
  for (int i = 0; i < (int)part.size(); i++) {
    int pl = part[i].first, pr = part[i].second;
    if (pl >= b) break;
    if (a >= pr) continue;
    if (a <= pl and pr <= b) {
      if (pl == pr - 1) {
        A[pl] += first[pl - a];
        sum[i] += first[pl - a];
        continue;
      }
      fi[i] += first[pl - a];
      se[i] += first[pl - a + 1];
      sum[i] += (dp[pr - a - 1] - (pl - a - 1 >= 0 ? dp[pl - a - 1] : 0)) % mod;
      fi[i] %= mod, se[i] %= mod, sum[i] %= mod;
      continue;
    }
    A[pl] += fi[i] % mod, A[pl + 1] += se[i] % mod;
    A[pl] %= mod, A[pl + 1] %= mod;
    if (a <= pl and pl < b)
      sum[i] += first[pl - a], A[pl] += first[pl - a], A[pl] %= mod,
          sum[i] %= mod;
    if (a <= pl + 1 and pl + 1 < b)
      sum[i] += first[pl + 1 - a], A[pl + 1] += first[pl + 1 - a],
          A[pl + 1] %= mod, sum[i] %= mod;
    for (int j = pl + 2; j < pr; j++) {
      int th = fi[i] + se[i];
      fi[i] = se[i], se[i] = th % mod;
      A[j] += se[i];
      A[j] %= mod;
      if (a <= j and j < b) {
        sum[i] += first[j - a];
        A[j] += first[j - a];
        A[j] %= mod, sum[i] %= mod;
      }
    }
    fi[i] = se[i] = 0;
  }
}
int get_sum(int a, int b) {
  int res = 0;
  for (int i = 0; i < (int)part.size(); i++) {
    int pl = part[i].first, pr = part[i].second;
    if (a >= pr) continue;
    if (pl >= b) break;
    if (a <= pl and pr <= b) {
      res += sum[i];
      res %= mod;
      continue;
    }
    A[pl] += fi[i], A[pl + 1] += se[i];
    A[pl] %= mod, A[pl + 1] %= mod;
    for (int j = pl + 2; j < pr; j++) {
      int th = fi[i] + se[i];
      fi[i] = se[i], se[i] = th % mod;
      A[j] += se[i];
      A[j] %= mod;
    }
    fi[i] = se[i] = 0;
    for (int j = pl; j < pr; j++) {
      if (a <= j and j < b) {
        res += A[j];
        res %= mod;
      }
    }
  }
  return res;
}
int main() {
  int m;
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++) scanf("%d", &A[i]);
  first[0] = first[1] = 1;
  dp[0] = 1, dp[1] = 2;
  for (int i = 2; i < n; i++)
    first[i] = first[i - 1] + first[i - 2], first[i] %= mod,
    dp[i] = (dp[i - 1] + first[i]) % mod;
  decom();
  while (m--) {
    int t, l, r;
    scanf("%d%d%d", &t, &l, &r);
    l--;
    if (t == 1)
      add(l, r);
    else
      printf("%d\n", (get_sum(l, r) + mod) % mod);
  }
  return 0;
}
