#include <bits/stdc++.h>
using namespace std;
const int Mod = 1e9 + 9;
const int N = 3e5 + 11;
long long fib[N];
template <class A>
void at(A& x) {
  if (x >= Mod) x %= Mod;
}
void init() {
  fib[1] = 1, fib[2] = 1;
  for (int i = 3; i < N; ++i) {
    fib[i] = fib[i - 1] + fib[i - 2];
    at(fib[i]);
  }
}
struct Segment {
  long long num[N << 2][2];
  long long sum[N << 2];
  long long ans;
  int x1, y1;
  int n;
  void init(int x) {
    n = x;
    build(1, 1, n);
  }
  void up(int u) {
    sum[u] = sum[u << 1] + sum[u << 1 | 1];
    at(sum[u]);
  }
  void build(int u, int l, int r) {
    num[u][0] = num[u][1] = 0;
    if (l == r) {
      scanf("%lld", &sum[u]);
      return;
    }
    build(u << 1, l, ((l + r) >> 1));
    build(u << 1 | 1, ((l + r) >> 1) + 1, r);
    up(u);
  }
  void update(int l, int r) {
    x1 = l, y1 = r;
    _update(1, 1, n);
  }
  void down(int u, int l, int r) {
    int u1 = (u << 1), u2 = (u << 1 | 1);
    num[u1][0] += num[u][0], num[u1][1] += num[u][1];
    at(num[u1][0]), at(num[u1][1]);
    long long a = num[u][0], b = num[u][1], len = ((l + r) >> 1) - l + 1 + 2;
    sum[u1] += b * fib[len - 1] + a * fib[len - 2] - b;
    at(sum[u1]);
    len = ((l + r) >> 1) - l + 2;
    long long a1 = b * fib[len - 1] + a * fib[len - 2],
              b1 = b * fib[len] + a * fib[len - 1];
    at(a1), at(b1);
    num[u2][0] += a1, num[u2][1] += b1;
    at(num[u2][0]), at(num[u2][1]);
    len = r - ((l + r) >> 1) + 2;
    sum[u2] += b1 * fib[len - 1] + a1 * fib[len - 2] - b1;
    at(sum[u2]);
    num[u][0] = num[u][1] = 0;
  }
  void _update(int u, int l, int r) {
    if (x1 <= l && r <= y1) {
      num[u][0] += fib[l - x1 + 1], num[u][1] += fib[l - x1 + 2];
      at(num[u][0]), at(num[u][1]);
      long long a = fib[l - x1 + 1], b = fib[l - x1 + 2], len = r - l + 1 + 2;
      sum[u] = sum[u] + b * fib[len - 1] + a * fib[len - 2] - b;
      at(sum[u]);
      return;
    }
    down(u, l, r);
    if (x1 <= ((l + r) >> 1)) _update(u << 1, l, ((l + r) >> 1));
    if (y1 > ((l + r) >> 1)) _update(u << 1 | 1, ((l + r) >> 1) + 1, r);
    up(u);
  }
  long long query(int l, int r) {
    x1 = l, y1 = r;
    ans = 0;
    _query(1, 1, n);
    return ans;
  }
  void _query(int u, int l, int r) {
    if (x1 <= l && r <= y1) {
      ans += sum[u];
      at(ans);
      return;
    }
    down(u, l, r);
    if (x1 <= ((l + r) >> 1)) _query(u << 1, l, ((l + r) >> 1));
    if (y1 > ((l + r) >> 1)) _query(u << 1 | 1, ((l + r) >> 1) + 1, r);
    up(u);
  }
} seg;
int n, m;
int main() {
  init();
  while (scanf("%d %d", &n, &m) == 2) {
    seg.init(n);
    int op, a, b;
    while (m--) {
      scanf("%d %d %d", &op, &a, &b);
      if (op == 1)
        seg.update(a, b);
      else
        printf("%lld\n", seg.query(a, b));
    }
  }
}
