#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 9;
const int maxn = 3e5 + 5;
struct Mat {
  long long a[2][2];
  Mat() {
    a[0][0] = a[0][1] = a[1][0] = 1;
    a[1][1] = 0;
  }
  Mat(int x, int y) {
    a[0][0] = x;
    a[1][0] = y;
    a[0][1] = a[1][1] = 0;
  }
  Mat operator*(const Mat &b) const {
    Mat ret;
    memset(ret.a, 0, sizeof(ret.a));
    for (int i = 0; i < 2; i++)
      for (int j = 0; j < 2; j++)
        for (int k = 0; k < 2; k++) {
          ret.a[i][j] += a[i][k] * b.a[k][j];
          ret.a[i][j] %= MOD;
        }
    return ret;
  }
} mt[maxn];
long long fa[maxn * 4], fb[maxn * 4];
long long sum[maxn * 4];
long long GetFbSum(long long a, long long b, long long n) {
  long long ret = (mt[n] * Mat(a, b)).a[0][0] - a;
  if (ret < 0) ret += MOD;
  return ret;
}
void GetFb(long long a, long long b, long long n, long long &x, long long &y) {
  Mat tmp = mt[n] * Mat(a, b);
  x = tmp.a[0][0];
  y = tmp.a[1][0];
}
void pushdown(int id, int l, int r) {
  if (fa[id] || fb[id]) {
    int m = r - l + 1;
    fa[id << 1] += fa[id];
    if (fa[id << 1] >= MOD) fa[id << 1] -= MOD;
    fb[id << 1] += fb[id];
    if (fb[id << 1] >= MOD) fb[id << 1] -= MOD;
    sum[id << 1] += GetFbSum(fa[id], fb[id], m - (m >> 1));
    if (sum[id << 1] >= MOD) sum[id << 1] -= MOD;
    long long ta, tb;
    GetFb(fa[id], fb[id], m - (m >> 1), ta, tb);
    fa[id << 1 | 1] += ta;
    if (fa[id << 1 | 1] >= MOD) fa[id << 1 | 1] -= MOD;
    fb[id << 1 | 1] += tb;
    if (fb[id << 1 | 1] >= MOD) fb[id << 1 | 1] -= MOD;
    sum[id << 1 | 1] += GetFbSum(ta, tb, m >> 1);
    if (sum[id << 1 | 1] >= MOD) sum[id << 1 | 1] -= MOD;
    fa[id] = fb[id] = 0;
  }
}
void pushup(int id) {
  sum[id] = sum[id << 1] + sum[id << 1 | 1];
  if (sum[id] >= MOD) sum[id] -= MOD;
}
void build(int id, int L, int R) {
  fa[id] = fb[id] = 0;
  if (L == R)
    cin >> sum[id];
  else {
    int mid = L + R >> 1;
    build(id << 1, L, mid);
    build(id << 1 | 1, mid + 1, R);
    pushup(id);
  }
}
void Operate(int id, int L, int R, int l, int r) {
  if (l <= L && R <= r) {
    long long ta, tb;
    GetFb(1, 1, L - l, ta, tb);
    fa[id] += ta;
    if (fa[id] >= MOD) fa[id] -= MOD;
    fb[id] += tb;
    if (fb[id] >= MOD) fb[id] -= MOD;
    sum[id] += GetFbSum(ta, tb, R - L + 1);
    if (sum[id] >= MOD) sum[id] -= MOD;
  } else {
    int mid = L + R >> 1;
    pushdown(id, L, R);
    if (l <= mid) Operate(id << 1, L, mid, l, r);
    if (mid < r) Operate(id << 1 | 1, mid + 1, R, l, r);
    pushup(id);
  }
}
long long Query(int id, int L, int R, int l, int r) {
  if (l <= L && R <= r)
    return sum[id];
  else {
    int mid = L + R >> 1;
    pushdown(id, L, R);
    long long ret = 0;
    if (l <= mid) ret += Query(id << 1, L, mid, l, r);
    if (mid < r) ret += Query(id << 1 | 1, mid + 1, R, l, r);
    if (ret >= MOD) ret -= MOD;
    return ret;
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  for (int i = 2; i < maxn; i++) mt[i] = mt[i - 1] * Mat();
  mt[0].a[0][1] = mt[0].a[1][0] = 0;
  mt[0].a[0][0] = mt[0].a[1][1] = 1;
  int n, m;
  cin >> n >> m;
  build(1, 1, n);
  while (m--) {
    int op, l, r;
    cin >> op >> l >> r;
    if (op == 1)
      Operate(1, 1, n, l, r);
    else
      cout << Query(1, 1, n, l, r) << endl;
  }
  return 0;
}
