#include <bits/stdc++.h>
using namespace std;
int key, x, y, n, m;
long long sum1[300001], sum2[300001];
long long a1[300001], a2[300001];
long long s[300001];
long long lazy1[2000001], lazy2[2000001];
long long sum[2000001];
void down(int p, int l, int r) {
  if (lazy1[p] || lazy2[p]) {
    int ll = p << 1, mid = (l + r) >> 1;
    long long tmp1 = (lazy1[p] * a1[mid - l + 2] % 1000000009 +
                      lazy2[p] * a2[mid - l + 2] % 1000000009) %
                     1000000009,
              tmp2 = (lazy1[p] * a1[mid - l + 3] % 1000000009 +
                      lazy2[p] * a2[mid - l + 3] % 1000000009) %
                     1000000009;
    sum[ll] = (sum[ll] + lazy1[p] * sum1[mid - l + 1] +
               lazy2[p] * sum2[mid - l + 1]) %
              1000000009;
    sum[ll + 1] = (sum[ll + 1] + tmp1 * sum1[r - mid] + tmp2 * sum2[r - mid]) %
                  1000000009;
    lazy1[ll] = (lazy1[ll] + lazy1[p]) % 1000000009;
    lazy1[ll + 1] = (lazy1[ll + 1] + tmp1) % 1000000009;
    lazy2[ll] = (lazy2[ll] + lazy2[p]) % 1000000009;
    lazy2[ll + 1] = (lazy2[ll + 1] + tmp2) % 1000000009;
    lazy1[p] = lazy2[p] = 0;
  }
}
void add(int p, int l, int r, int x, int y, long long z1, long long z2) {
  z1 %= 1000000009;
  z2 %= 1000000009;
  if (l == x && r == y) {
    sum[p] = (sum[p] + z1 * sum1[r - l + 1] % 1000000009 +
              z2 * sum2[r - l + 1] % 1000000009) %
             1000000009;
    lazy1[p] += z1;
    lazy2[p] += z2;
    lazy1[p] %= 1000000009;
    lazy2[p] %= 1000000009;
    return;
  }
  down(p, l, r);
  int mid = (l + r) >> 1, ll = p << 1;
  if (y <= mid)
    add(ll, l, mid, x, y, z1, z2);
  else if (x >= mid + 1)
    add(ll + 1, mid + 1, r, x, y, z1, z2);
  else {
    add(ll, l, mid, x, mid, z1, z2);
    add(ll + 1, mid + 1, r, mid + 1, y,
        (z1 * a1[mid - x + 2]) % 1000000009 +
            (z2 * a2[mid - x + 2]) % 1000000009,
        (z1 * a1[mid - x + 3]) % 1000000009 +
            (z2 * a2[mid - x + 3]) % 1000000009);
  }
  sum[p] = (sum[ll] + sum[ll + 1]) % 1000000009;
}
int query(int p, int l, int r, int x, int y) {
  if (l == x && r == y) return sum[p] % 1000000009;
  down(p, l, r);
  int mid = (l + r) >> 1, ll = p << 1;
  if (y <= mid)
    return query(ll, l, mid, x, y);
  else if (x >= mid + 1)
    return query(ll + 1, mid + 1, r, x, y);
  else
    return (query(ll, l, mid, x, mid) + query(ll + 1, mid + 1, r, mid + 1, y)) %
           1000000009;
}
int main() {
  scanf("%d%d", &n, &m);
  a1[1] = 1;
  a2[1] = 0;
  a1[2] = 0;
  a2[2] = 1;
  for (int i = 3; i <= n; i++) {
    a1[i] = (a1[i - 2] + a1[i - 1]) % 1000000009;
    a2[i] = (a2[i - 2] + a2[i - 1]) % 1000000009;
  }
  for (int i = 1; i <= n; i++) {
    sum1[i] = (a1[i] + sum1[i - 1]) % 1000000009;
    sum2[i] = (a2[i] + sum2[i - 1]) % 1000000009;
  }
  for (int i = 1; i <= n; i++) {
    scanf("%I64d", &s[i]);
    s[i] = (s[i] + s[i - 1]) % 1000000009;
  }
  for (int i = 1; i <= m; i++) {
    scanf("%d%d%d", &key, &x, &y);
    if (key == 1) {
      add(1, 1, n, x, y, 1, 1);
    }
    if (key == 2)
      printf("%I64d\n", ((s[y] - s[x - 1]) % 1000000009 + 1000000009 +
                         query(1, 1, n, x, y)) %
                            1000000009);
  }
}
