#include <bits/stdc++.h>
using namespace std;
template <typename T>
T mabs(const T &a) {
  return a < 0 ? -a : a;
}
const int mod = 1e9 + 9;
const int SZ = 300300;
struct mat {
  long long A[2][2];
  mat(int a = 0, int b = 0, int c = 0, int d = 0) {
    A[0][0] = a;
    A[0][1] = b;
    A[1][0] = c;
    A[1][1] = d;
  }
  mat operator*(const mat &other) const {
    mat res;
    for (int i = (0), ei = (2); i < ei; i++)
      for (int j = (0), ej = (2); j < ej; j++) {
        for (int k = (0), ek = (2); k < ek; k++)
          res.A[i][j] += A[i][k] * other.A[k][j];
        res.A[i][j] %= mod;
      }
    return res;
  }
  mat operator+(const mat &other) const {
    mat res;
    for (int i = (0), ei = (2); i < ei; i++)
      for (int j = (0), ej = (2); j < ej; j++) {
        res.A[i][j] = A[i][j] + other.A[i][j];
        res.A[i][j] %= mod;
      }
    return res;
  }
  mat operator-(const mat &other) const {
    mat res;
    for (int i = (0), ei = (2); i < ei; i++)
      for (int j = (0), ej = (2); j < ej; j++) {
        res.A[i][j] = A[i][j] - other.A[i][j];
        res.A[i][j] %= mod;
      }
    return res;
  }
};
mat Fib(1, 1, 1, 0);
mat EminusArev(-1, -1, -1, 0);
mat Step[SZ];
long long Sum[4 * SZ];
mat M[4 * SZ];
int A[SZ];
void build(int v, int l, int r) {
  if (l == r) {
    Sum[v] = A[l];
    return;
  }
  int c = (l + r) / 2;
  build(2 * v, l, c);
  build(2 * v + 1, c + 1, r);
  Sum[v] = (Sum[2 * v] + Sum[2 * v + 1]) % mod;
}
inline mat sumUp(int a, int b) {
  mat res = EminusArev * (Step[0] - Step[b - a + 1]);
  return Step[a] * res;
}
void add(int v, int l, int r, int ql, int qr, int st) {
  Sum[v] = (Sum[v] + sumUp(ql - st, qr - st).A[0][0]) % mod;
  if (l == ql && r == qr) {
    M[v] = M[v] + Step[ql - st];
    return;
  }
  int c = (l + r) / 2;
  if (qr <= c)
    add(2 * v, l, c, ql, qr, st);
  else if (ql > c)
    add(2 * v + 1, c + 1, r, ql, qr, st);
  else {
    add(2 * v, l, c, ql, c, st);
    add(2 * v + 1, c + 1, r, c + 1, qr, st);
  }
}
long long getSum(int v, int l, int r, int ql, int qr) {
  if (l == ql && r == qr) {
    return Sum[v];
  }
  int c = (l + r) / 2;
  long long res = 0;
  if (qr <= c)
    res = getSum(2 * v, l, c, ql, qr);
  else if (ql > c)
    res = getSum(2 * v + 1, c + 1, r, ql, qr);
  else
    res = getSum(2 * v, l, c, ql, c) + getSum(2 * v + 1, c + 1, r, c + 1, qr);
  return (res + (M[v] * sumUp(ql - l, qr - l)).A[0][0]) % mod;
}
void run() {
  Step[0] = mat(1, 0, 0, 1);
  for (int i = (1), ei = (SZ); i < ei; i++) Step[i] = Step[i - 1] * Fib;
  int n, m;
  cin >> n >> m;
  for (int i = (0), ei = (n); i < ei; i++) scanf("%d", A + i);
  build(1, 0, n - 1);
  for (int i = (0), ei = (m); i < ei; i++) {
    int t, a, b;
    scanf("%d%d%d", &t, &a, &b);
    --a;
    --b;
    if (t == 1) {
      add(1, 0, n - 1, a, b, a);
    } else {
      int res = getSum(1, 0, n - 1, a, b);
      res = (res + mod) % mod;
      printf("%d\n", res);
    }
  }
}
int main() {
  run();
  return 0;
}
