#include <bits/stdc++.h>
const int N = 1e6 + 5, P = 1e9 + 9;
inline int ksm(int a, int b) {
  int r = 1;
  for (; b; b >>= 1, a = (long long)a * a % P)
    if (b & 1) r = (long long)r * a % P;
  return r;
}
int n, q, a[N], t[N], f[N], F[N];
struct mat {
  int s[2][2];
  inline friend mat operator+(mat a, mat b) {
    return a.s[0][0] = (a.s[0][0] + b.s[0][0]) % P,
           a.s[0][1] = (a.s[0][1] + b.s[0][1]) % P,
           a.s[1][0] = (a.s[1][0] + b.s[1][0]) % P,
           a.s[1][1] = (a.s[1][1] + b.s[1][1]) % P, a;
  }
  inline friend mat operator*(mat a, mat b) {
    mat c;
    c.s[0][0] =
        ((long long)a.s[0][0] * b.s[0][0] + (long long)a.s[0][1] * b.s[1][0]) %
        P,
    c.s[0][1] =
        ((long long)a.s[0][0] * b.s[0][1] + (long long)a.s[0][1] * b.s[1][1]) %
        P,
    c.s[1][0] =
        ((long long)a.s[1][0] * b.s[0][0] + (long long)a.s[1][1] * b.s[1][0]) %
        P,
    c.s[1][1] =
        ((long long)a.s[1][0] * b.s[0][1] + (long long)a.s[1][1] * b.s[1][1]) %
        P;
    return c;
  }
  inline friend bool operator!=(mat a, mat b) {
    return a.s[0][0] != b.s[0][0] || a.s[0][1] != b.s[0][1] ||
           a.s[1][0] != b.s[1][0] || a.s[1][1] != b.s[1][1];
  }
  inline bool INV(mat &b) {
    long long x = (long long)s[0][0] * s[1][1] - (long long)s[0][1] * s[1][0];
    if (!x) return 0;
    if (x > 0)
      x = ksm(x % P, P - 2), b.s[0][0] = (long long)x * s[1][1] % P,
      b.s[1][1] = x * s[0][0] % P, b.s[0][1] = x * (P - s[0][1]) % P,
      b.s[1][0] = x * (P - s[1][0]) % P;
    else
      x = ksm((-x) % P, P - 2), b.s[0][0] = (long long)x * (P - s[1][1]) % P,
      b.s[1][1] = x * (P - s[0][0]) % P, b.s[0][1] = x * s[0][1] % P,
      b.s[1][0] = x * s[1][0] % P;
    return 1;
  }
} E, Z, O, lz[N];
inline mat ksm(mat a, int b) {
  mat r = E;
  for (; b; b >>= 1, a = a * a)
    if (b & 1) r = r * a;
  return r;
}
inline int sum(int l, int r, mat v) {
  return ((long long)(F[r] - F[l - 1] + P) * v.s[1][1] +
          (long long)(F[r + 1] - F[l] + P) * v.s[1][0]) %
         P;
}
inline void tg(int p, int l, int r, mat v) {
  lz[p] = lz[p] + v, t[p] = (t[p] + sum(l, r, v)) % P;
}
inline void pushdown(int p, int l, int r, int mid) {
  if (lz[p] != O)
    tg(p << 1, l, mid, lz[p]), tg(p << 1 | 1, mid + 1, r, lz[p]), lz[p] = O;
}
inline void build(int p, int l, int r) {
  if (l == r) {
    t[p] = a[l];
    return;
  }
  int mid = l + r >> 1;
  build(p << 1, l, mid), build(p << 1 | 1, mid + 1, r),
      t[p] = (t[p << 1] + t[p << 1 | 1]) % P;
}
inline void add(int p, int l, int r, int x, int y, mat v) {
  if (l >= x && r <= y) return tg(p, l, r, v);
  int mid = l + r >> 1;
  pushdown(p, l, r, mid);
  if (x <= mid) add(p << 1, l, mid, x, y, v);
  if (y > mid) add(p << 1 | 1, mid + 1, r, x, y, v);
  t[p] = (t[p << 1] + t[p << 1 | 1]) % P;
}
inline int query(int p, int l, int r, int x, int y) {
  if (l >= x && r <= y) return t[p];
  int mid = l + r >> 1, res = 0;
  pushdown(p, l, r, mid);
  if (x <= mid) res = (res + query(p << 1, l, mid, x, y)) % P;
  if (y > mid) res = (res + query(p << 1 | 1, mid + 1, r, x, y)) % P;
  return res;
}
int main() {
  scanf("%d%d", &n, &q);
  int i, l, r, v;
  mat x, y;
  for (i = 1; i <= n; i++) scanf("%d", a + i);
  build(1, 1, n);
  for (f[1] = f[2] = 1, i = 3; i < N; i++) f[i] = (f[i - 1] + f[i - 2]) % P;
  for (i = 1; i < N; i++) F[i] = (F[i - 1] + f[i]) % P;
  E.s[0][0] = E.s[1][1] = Z.s[0][0] = Z.s[0][1] = Z.s[1][0] = 1;
  while (q--)
    if (scanf("%d%d%d", &i, &l, &r), i > 1)
      printf("%d\n", query(1, 1, n, l, r));
    else
      x = ksm(Z, l - 1), x.INV(y) && (add(1, 1, n, l, r, y), 0);
  return 0;
}
