#include <bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
pair<long long, long long> zero;
long long fib[300010];
void getFib() {
  fib[1] = 1LL;
  for (long long i = (2); i < (300010); ++i)
    fib[i] = (fib[i - 1] + fib[i - 2]) % 1000000009LL;
}
long long segTree[1 << 20];
pair<long long, long long> lazyTree[1 << 20];
long long arr[300010];
void buildTree(int low, int high, int pos) {
  int mid = (low + high) >> 1;
  if (low == high)
    segTree[pos] = arr[mid];
  else {
    buildTree(low, mid, 2 * pos + 1);
    buildTree(mid + 1, high, 2 * pos + 2);
    segTree[pos] = (segTree[2 * pos + 1] + segTree[2 * pos + 2]) % 1000000009LL;
  }
}
void updateTree(int low, int high, int pos, int qLow, int qHigh) {
  int mid = (low + high) >> 1;
  if (lazyTree[pos] != zero) {
    int n = high - low + 1;
    long long a = lazyTree[pos].first;
    long long b = lazyTree[pos].second;
    int rChild = mid - low + 2;
    segTree[pos] = (segTree[pos] + (a * fib[n]) % 1000000009LL +
                    (b * fib[n + 1]) % 1000000009LL - b + 1000000009LL) %
                   1000000009LL;
    if (low != high) {
      lazyTree[2 * pos + 1] =
          make_pair((lazyTree[2 * pos + 1].first + a) % 1000000009LL,
                    (lazyTree[2 * pos + 1].second + b) % 1000000009LL);
      lazyTree[2 * pos + 2] =
          make_pair((lazyTree[2 * pos + 2].first + a * fib[rChild - 2] +
                     b * fib[rChild - 1]) %
                        1000000009LL,
                    (lazyTree[2 * pos + 2].second + a * fib[rChild - 1] +
                     b * fib[rChild]) %
                        1000000009LL);
    }
    lazyTree[pos] = zero;
  }
  if (qLow > high || qHigh < low)
    return;
  else if (qLow <= low && qHigh >= high) {
    int n = high - low + 1;
    long long a = fib[low - qLow + 1];
    long long b = fib[low - qLow + 2];
    int rChild = mid - low + 2;
    segTree[pos] = (segTree[pos] + (a * fib[n]) % 1000000009LL +
                    (b * fib[n + 1]) % 1000000009LL - b + 1000000009LL) %
                   1000000009LL;
    if (low != high) {
      lazyTree[2 * pos + 1] =
          make_pair((lazyTree[2 * pos + 1].first + a) % 1000000009LL,
                    (lazyTree[2 * pos + 1].second + b) % 1000000009LL);
      lazyTree[2 * pos + 2] =
          make_pair((lazyTree[2 * pos + 2].first + a * fib[rChild - 2] +
                     b * fib[rChild - 1]) %
                        1000000009LL,
                    (lazyTree[2 * pos + 2].second + a * fib[rChild - 1] +
                     b * fib[rChild]) %
                        1000000009LL);
    }
  } else {
    updateTree(low, mid, 2 * pos + 1, qLow, qHigh);
    updateTree(mid + 1, high, 2 * pos + 2, qLow, qHigh);
    segTree[pos] = (segTree[2 * pos + 1] + segTree[2 * pos + 2]) % 1000000009LL;
  }
}
long long queryTree(int low, int high, int pos, int qLow, int qHigh) {
  int mid = (low + high) >> 1;
  if (lazyTree[pos] != zero) {
    int n = high - low + 1;
    long long a = lazyTree[pos].first;
    long long b = lazyTree[pos].second;
    int rChild = mid - low + 2;
    segTree[pos] = (segTree[pos] + (a * fib[n]) % 1000000009LL +
                    (b * fib[n + 1]) % 1000000009LL - b + 1000000009LL) %
                   1000000009LL;
    if (low != high) {
      lazyTree[2 * pos + 1] =
          make_pair((lazyTree[2 * pos + 1].first + a) % 1000000009LL,
                    (lazyTree[2 * pos + 1].second + b) % 1000000009LL);
      lazyTree[2 * pos + 2] =
          make_pair((lazyTree[2 * pos + 2].first + a * fib[rChild - 2] +
                     b * fib[rChild - 1]) %
                        1000000009LL,
                    (lazyTree[2 * pos + 2].second + a * fib[rChild - 1] +
                     b * fib[rChild]) %
                        1000000009LL);
    }
    lazyTree[pos] = zero;
  }
  if (qLow > high || qHigh < low)
    return 0LL;
  else if (qLow <= low && qHigh >= high)
    return segTree[pos];
  else
    return (queryTree(low, mid, 2 * pos + 1, qLow, qHigh) +
            queryTree(mid + 1, high, 2 * pos + 2, qLow, qHigh)) %
           1000000009LL;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  getFib();
  int n, m;
  cin >> n >> m;
  for (long long i = 0; i < (n); ++i) cin >> arr[i];
  buildTree(0, n - 1, 0);
  for (long long i = 0; i < (m); ++i) {
    int q, l, r;
    cin >> q >> l >> r;
    --l;
    --r;
    if (q == 1)
      updateTree(0, n - 1, 0, l, r);
    else
      cout << queryTree(0, n - 1, 0, l, r) << '\n';
  }
  return 0;
}
