#include <bits/stdc++.h>
using namespace std;
long long mod = 1000000009;
long long f[300100], g[300100], sumF[300100], sumG[300100];
long long tree[1300100];
pair<long long, long long> lazy[1300100];
long long sum[300100];
void precompute() {
  f[1] = 1, f[2] = 0;
  g[1] = 0, g[2] = 1;
  sumF[1] = 1, sumF[2] = 1;
  sumG[1] = 0, sumG[2] = 1;
  for (int i = 3; i <= 300000; i++) {
    f[i] = (f[i - 1] + f[i - 2]) % mod;
    g[i] = (g[i - 1] + g[i - 2]) % mod;
    sumF[i] = (sumF[i - 1] + f[i]) % mod;
    sumG[i] = (sumG[i - 1] + g[i]) % mod;
  }
}
long long getFib(long long a, long long b, long long c) {
  return (((a * f[c]) % mod) + (b * g[c]) % mod) % mod;
}
void propagate(int node, int a, int b) {
  if (lazy[node].first || lazy[node].second) {
    long long x = lazy[node].first;
    long long y = lazy[node].second;
    tree[node] = (tree[node] + ((x * sumF[b - a + 1]) % mod)) % mod;
    tree[node] = (tree[node] + ((y * sumG[b - a + 1]) % mod)) % mod;
    lazy[node * 2].first = (lazy[node * 2].first + x) % mod;
    lazy[node * 2].second = (lazy[node * 2].second + y) % mod;
    int mid = (a + b) / 2;
    lazy[node * 2 + 1].first =
        (lazy[node * 2 + 1].first + getFib(x, y, mid - a + 2)) % mod;
    lazy[node * 2 + 1].second =
        (lazy[node * 2 + 1].second + getFib(x, y, mid - a + 3)) % mod;
    lazy[node] = make_pair(0, 0);
  }
}
void update(int node, int a, int b, int i, int j) {
  propagate(node, a, b);
  if (a > b || a > j || b < i) return;
  if (a >= i && b <= j) {
    lazy[node].first = (lazy[node].first + getFib(1, 1, a - i + 1)) % mod;
    lazy[node].second = (lazy[node].second + getFib(1, 1, a - i + 2)) % mod;
    propagate(node, a, b);
    return;
  }
  update(node * 2, a, (a + b) / 2, i, j);
  update(node * 2 + 1, (a + b) / 2 + 1, b, i, j);
  tree[node] = (tree[node * 2] + tree[node * 2 + 1]) % mod;
}
long long query(int node, int a, int b, int i, int j) {
  propagate(node, a, b);
  if (a > b || a > j || b < i) return 0;
  if (a >= i && b <= j) return tree[node];
  long long q1 = query(node * 2, a, (a + b) / 2, i, j);
  long long q2 = query(node * 2 + 1, (a + b) / 2 + 1, b, i, j);
  return (q1 + q2) % mod;
}
int main() {
  long long n, m, q, x, y;
  scanf("%lld %lld", &n, &q);
  for (int i = 1; i <= n; i++) {
    scanf("%lld\n", &x);
    sum[i] = (sum[i - 1] + x) % mod;
  }
  precompute();
  while (q--) {
    scanf("%lld %lld %lld", &m, &x, &y);
    if (m == 1)
      update(1, 1, n, x, y);
    else {
      long long ans = query(1, 1, n, x, y);
      cout << (ans + sum[y] - sum[x - 1] + mod) % mod << endl;
    }
  }
  return 0;
}
