#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
template <int MODP>
struct Int {
  int64 x;
  Int() : x(0) {}
  Int(int64 x) : x(x) {
    x %= MODP;
    if (x < 0) x += MODP;
  }
  static Int wrap(int64 x) {
    Int a;
    a.x = x;
    return a;
  }
  Int operator+(const Int& o) const {
    auto t = x + o.x;
    if (t >= MODP) t -= MODP;
    return wrap(t);
  }
  Int operator-(const Int& o) const {
    auto t = x - o.x;
    if (t < 0) t += MODP;
    return wrap(t);
  }
  Int operator-() const { return wrap(MODP - x); }
  Int operator*(const Int& o) const { return wrap(1LL * x * o.x % MODP); }
  Int operator/(const Int& o) const { return *this * o.inv(); }
  Int& operator+=(const Int& o) { return *this = *this + o; }
  Int& operator-=(const Int& o) { return *this = *this - o; }
  Int& operator*=(const Int& o) { return *this = *this * o; }
  Int& operator/=(const Int& o) { return *this = *this / o; }
  Int pow(int64 n) const {
    if (!n) return wrap(1);
    const auto& a = *this;
    if (n & 1)
      return pow(n - 1) * a;
    else
      return (a * a).pow(n / 2);
  }
  Int inv() const { return pow(MODP - 2); }
  bool operator==(const Int& o) const { return x == o.x; }
  bool operator!=(const Int& o) const { return x != o.x; }
};
const int MAX_N = 3e5 + 5, MOD = 1e9 + 9;
using IntM = Int<MOD>;
int N, M;
namespace Fib {
IntM Sum[MAX_N];
void init() {
  Sum[2] = IntM::wrap(1);
  for (int k{3}, _end{N + 5}; k < _end; ++k) {
    Sum[k] = Sum[k - 1] + Sum[k - 2];
  }
  for (int k{0}, _end{N + 5}; k < _end; ++k) {
    Sum[k] += Sum[k - 1];
  }
}
IntM fib(int n) {
  int nn = abs(n);
  auto res = Sum[nn + 1] - Sum[nn];
  if (n < 0 && !(n & 1)) res = -res;
  return res;
}
struct Tree {
  Tree *pl, *pr;
  int l, r;
  IntM lazA, lazB, sum;
  Tree(int l, int r, const vector<int>& A) : pl(0), pr(0), l(l), r(r) {
    if (l + 1 == r) {
      sum = A[l];
      return;
    }
    int m = l + (r - l) / 2;
    pl = new Tree(l, m, A);
    pr = new Tree(m, r, A);
    up();
  }
  void down() {
    if (lazA.x == 0 && lazB.x == 0) return;
    sum += lazA * (Sum[r + 2] - Sum[l + 2]) + lazB * (Sum[r + 1] - Sum[l + 1]);
    if (pl) {
      pl->lazA += lazA, pl->lazB += lazB;
      pr->lazA += lazA, pr->lazB += lazB;
    }
    lazA.x = 0, lazB.x = 0;
  }
  void up() { sum = pl->sum + pr->sum; }
  void update(int L, int R) {
    down();
    if (r <= L || R <= l) return;
    if (L <= l && r <= R) {
      lazA += fib(-L), lazB += fib(-L - 1);
      down();
      return;
    }
    pl->update(L, R);
    pr->update(L, R);
    up();
  }
  IntM query(int L, int R) {
    down();
    if (r <= L || R <= l) return IntM::wrap(0);
    if (L <= l && r <= R) return sum;
    return pl->query(L, R) + pr->query(L, R);
  }
};
}  // namespace Fib
int main() {
  cin >> N >> M;
  vector<int> A(N);
  for (int& x : A) {
    cin >> x;
  }
  Fib::init();
  auto seg = new Fib::Tree(0, N, A);
  for (int i{0}, _end{M}; i < _end; ++i) {
    int q, L, R;
    cin >> q >> L >> R;
    --L;
    if (q == 1)
      seg->update(L, R);
    else
      cout << seg->query(L, R).x << "\n";
  }
  return 0;
}
