#include <bits/stdc++.h>
using namespace std;
const int MAXN = (int)3e5 + 5;
const int MOD = (int)1e9 + 9;
struct Mat {
  long long int m[2][2];
  Mat() {
    for (int i = 0; i < 2; i++) {
      for (int j = 0; j < 2; j++) {
        m[i][j] = 0;
      }
    }
  }
  Mat(bool id) {
    for (int i = 0; i < 2; i++) {
      for (int j = 0; j < 2; j++) {
        m[i][j] = 1;
      }
    }
    if (id) {
      m[0][1] = m[1][0] = 0;
    } else {
      m[1][1] = 0;
    }
  }
  Mat operator*(const Mat& a) {
    Mat ans = Mat{};
    for (int i = 0; i < 2; i++) {
      for (int j = 0; j < 2; j++) {
        for (int k = 0; k < 2; k++) {
          ans.m[i][j] += m[i][k] * a.m[k][j];
          ans.m[i][j] %= MOD;
        }
      }
    }
    return ans;
  }
  Mat operator+(const Mat& a) {
    Mat ans = Mat{};
    for (int i = 0; i < 2; i++) {
      for (int j = 0; j < 2; j++) {
        ans.m[i][j] += m[i][j] + a.m[i][j];
        if (ans.m[i][j] > MOD) {
          ans.m[i][j] -= MOD;
        }
      }
    }
    return ans;
  }
};
struct Node {
  long long int sum;
  long long int Aup, Bup;
  Node() { sum = Aup = Bup = 0; }
};
long long int a[MAXN];
Mat pw[MAXN];
Mat sum_pw[MAXN];
Node tree[4 * MAXN];
void pushdown(int node, int a, int b, long long int Aup, long long int Bup) {
  if (a == b) {
    return;
  }
  int mid = (a + b) / 2;
  tree[node * 2].Aup += Aup;
  tree[node * 2].Bup += Bup;
  tree[node * 2].Aup %= MOD;
  tree[node * 2].Bup %= MOD;
  long long int nAup =
      (pw[mid - a + 1].m[1][0] * Bup + pw[mid - a + 1].m[1][1] * Aup) % MOD;
  long long int nBup =
      (pw[mid - a + 1].m[0][0] * Bup + pw[mid - a + 1].m[0][1] * Aup) % MOD;
  tree[node * 2 + 1].Aup += nAup;
  tree[node * 2 + 1].Aup %= MOD;
  tree[node * 2 + 1].Bup += nBup;
  tree[node * 2 + 1].Bup %= MOD;
  return;
}
void resolve_lazy(int node, int a, int b) {
  if (tree[node].Aup != 0 || tree[node].Bup != 0) {
    tree[node].sum += sum_pw[b - a].m[1][0] * tree[node].Bup +
                      sum_pw[b - a].m[1][1] * tree[node].Aup;
    tree[node].sum %= MOD;
    pushdown(node, a, b, tree[node].Aup, tree[node].Bup);
    tree[node].Aup = tree[node].Bup = 0;
  }
  return;
}
void update(int node, int a, int b, int l, int r, long long int Aup,
            long long int Bup) {
  resolve_lazy(node, a, b);
  if (b < l || a > r || a > b) {
    return;
  }
  if (l <= a && b <= r) {
    tree[node].sum += sum_pw[b - a].m[1][0] * Bup + sum_pw[b - a].m[1][1] * Aup;
    tree[node].sum %= MOD;
    pushdown(node, a, b, Aup, Bup);
    return;
  }
  int mid = (a + b) / 2;
  update(node * 2, a, mid, l, r, Aup, Bup);
  long long int nAup = (pw[max(0, mid - max(a, l) + 1)].m[1][0] * Bup +
                        pw[max(0, mid - max(a, l) + 1)].m[1][1] * Aup) %
                       MOD;
  long long int nBup = (pw[max(0, mid - max(a, l) + 1)].m[0][0] * Bup +
                        pw[max(0, mid - max(a, l) + 1)].m[0][1] * Aup) %
                       MOD;
  update(node * 2 + 1, mid + 1, b, l, r, nAup, nBup);
  tree[node].sum = tree[node * 2].sum + tree[node * 2 + 1].sum;
  tree[node].sum %= MOD;
  return;
}
long long int query(int node, int a, int b, int l, int r) {
  resolve_lazy(node, a, b);
  if (b < l || a > r || a > b) {
    return 0;
  }
  if (l <= a && b <= r) {
    return tree[node].sum;
  }
  int mid = (a + b) / 2;
  long long int q1 = query(node * 2, a, mid, l, r);
  long long int q2 = query(node * 2 + 1, mid + 1, b, l, r);
  return (q1 + q2) % MOD;
}
int main(void) {
  int n, m;
  int op, l, r;
  scanf(" %d %d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf(" %lld", &a[i]);
    a[i] += a[i - 1];
  }
  pw[0] = Mat(true);
  pw[1] = Mat(false);
  for (int i = 2; i <= n; i++) {
    pw[i] = pw[i - 1] * pw[1];
  }
  sum_pw[0] = Mat(true);
  for (int i = 1; i <= n; i++) {
    sum_pw[i] = pw[i] + sum_pw[i - 1];
  }
  while (m--) {
    scanf(" %d %d %d", &op, &l, &r);
    if (op == 1) {
      update(1, 1, n, l, r, 1, 1);
    } else {
      long long int ans = (a[r] - a[l - 1] + query(1, 1, n, l, r)) % MOD;
      printf("%lld\n", ans);
    }
  }
  return 0;
}
