#include <bits/stdc++.h>
using namespace std;
#pragma GCC target("sse4.2")
long long gcd(long long n, long long m) {
  if (n == 0) return m;
  return gcd(m % n, n);
}
bool ifprime(long long n) {
  if (n == 1) return false;
  long long i;
  for (i = 2; i * i <= n; i++) {
    if (n % i == 0) return false;
  }
  return true;
}
void disp(vector<long long> v) {
  for (auto u : v) cout << u << " ";
  cout << "\n";
}
void remleadzero(vector<int>& v) {
  vector<int> u;
  int i = 0;
  while (v[i] == 0) i++;
  while (i < v.size()) {
    u.push_back(v[i]);
    i++;
  }
  v = u;
}
long long fast_expo(long long n, long long m, long long md) {
  long long a = 1;
  while (m > 0) {
    if (m & 1) a = (a * n) % md;
    n = (n * n) % md;
    m /= 2;
  }
  return a % md;
}
inline long long sqroot(long long n) {
  long double N = n;
  N = sqrtl(N);
  long long sq = N - 2;
  sq = max(sq, 0LL);
  while (sq * sq < n) {
    sq++;
  }
  if ((sq * sq) == n) return sq;
  return -1;
}
inline long long sqroot1(long long n) {
  long double N = n;
  N = sqrtl(N);
  long long sq = N - 2;
  sq = max(sq, 0LL);
  while (sq * sq < n) {
    sq++;
  }
  if ((sq * sq) == n) return sq;
  return sq - 1;
}
inline long long cbroot(long long n) {
  long double N = n;
  N = cbrtl(N);
  long long cb = N - 2;
  cb = max(cb, 0LL);
  while (cb * cb * cb < n) {
    cb++;
  }
  if ((cb * cb * cb) == n) return cb;
  return -1;
}
inline long long cbroot1(long long n) {
  long double N = n;
  N = cbrtl(N);
  long long cb = N - 2;
  cb = max(cb, 0LL);
  while (cb * cb * cb < n) {
    cb++;
  }
  if ((cb * cb * cb) == n) return cb;
  return cb - 1;
}
int dig_sum(long long n) {
  int ret = 0;
  while (n > 0) {
    ret += (n % 10);
    n /= 10;
  }
  return ret;
}
int sq(int x) { return x * x; }
long long dec(string s) {
  long long ret = 0;
  for (auto u : s) {
    ret <<= 1;
    ret += (u - '0');
  }
  return ret;
}
int gcd(int n, int m) {
  if (n == 0) return m;
  return gcd(m % n, n);
}
string update(string s) {
  int n = s.size();
  if (n < 2) return s;
  string ret = "";
  for (int i = 0; i < n; i++) {
    if (i < n - 1 and s[i] == ')' and s[i + 1] == '(') {
      i++;
      continue;
    }
    ret += s[i];
  }
  return ret;
}
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
long long rand_num(long long n) {
  long long random_number = uniform_int_distribution<long long>(0, n - 1)(rng);
  return random_number;
}
chrono::high_resolution_clock::time_point start;
chrono::high_resolution_clock::time_point cur_time;
int F1, F2;
pair<long long, long long> fib(int n) {
  if (n == 0) return {0, 1};
  auto p = fib(n >> 1);
  long long c =
      p.first * ((2 * p.second - p.first + 1000000009LL) % 1000000009LL);
  long long d = p.first * p.first + p.second * p.second;
  if (n & 1)
    return {d % 1000000009LL, (c + d) % 1000000009LL};
  else
    return {c % 1000000009LL, d % 1000000009LL};
}
int fibo(int n) {
  pair<int, int> f = fib(n);
  long long a0 = (f.second - f.first + 1000000009LL) % 1000000009LL,
            a1 = f.first, a2 = f.second;
  return (F1 * a0 + F2 * a1) % 1000000009LL;
}
const int maxn = 3e5;
const int BLOCK = 500;
int a[maxn], f[maxn + 2];
int BL[maxn];
pair<int, int> b[maxn];
int sum[maxn];
void update(int l, int r) {
  int b1 = BL[l], b2 = BL[r];
  if (b1 == b2) {
    for (int i = l; i <= r; i++) {
      a[i] += f[i - l];
      if (a[i] >= 1000000009LL) a[i] -= 1000000009LL;
      sum[BL[i]] += f[i - l];
      if (sum[BL[i]] >= 1000000009LL) sum[BL[i]] -= 1000000009LL;
    }
  } else {
    for (int i = l; i < (b1 + 1) * BLOCK; i++) {
      a[i] += f[i - l];
      if (a[i] >= 1000000009LL) a[i] -= 1000000009LL;
      sum[BL[i]] += f[i - l];
      if (sum[BL[i]] >= 1000000009LL) sum[BL[i]] -= 1000000009LL;
    }
    for (int i = (b1 + 1); i < b2; i++) {
      b[i].first += f[i * BLOCK - l];
      if (b[i].first >= 1000000009LL) b[i].first -= 1000000009LL;
      b[i].second += f[i * BLOCK - l + 1];
      if (b[i].second >= 1000000009LL) b[i].second -= 1000000009LL;
      sum[i] +=
          ((f[(i + 1) * BLOCK + 1 - l] - f[i * BLOCK + 1 - l] + 1000000009LL) %
           1000000009LL);
      if (sum[i] >= 1000000009LL) sum[i] -= 1000000009LL;
    }
    for (int i = b2 * BLOCK; i <= r; i++) {
      a[i] += f[i - l];
      if (a[i] >= 1000000009LL) a[i] -= 1000000009LL;
      sum[BL[i]] += f[i - l];
      if (sum[BL[i]] >= 1000000009LL) sum[BL[i]] -= 1000000009LL;
    }
  }
}
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
  cout << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
  const char* comma = strchr(names + 1, ',');
  cout.write(names, comma - names) << " : " << arg1 << " | ";
  __f(comma + 1, args...);
}
int query(int l, int r) {
  int b1 = BL[l], b2 = BL[r];
  int ans = 0;
  if (b1 == b2) {
    for (int i = l; i <= r; i++) {
      ans += a[i];
      if (ans >= 1000000009LL) ans -= 1000000009LL;
    }
    F1 = b[b1].first, F2 = b[b1].second;
    int F = fibo(l - b1 * BLOCK), S = -1;
    ans += F;
    if (ans >= 1000000009LL) ans -= 1000000009LL;
    if (r >= l + 1) {
      S = fibo(l + 1 - b1 * BLOCK);
      ans += S;
      if (ans >= 1000000009LL) ans -= 1000000009LL;
    }
    for (int i = l + 2; i <= r; i++) {
      int T = (F + S) % 1000000009LL;
      ans += T;
      assert(T >= 0);
      if (ans >= 1000000009LL) ans -= 1000000009LL;
      F = S;
      S = T;
    }
  } else {
    F1 = b[b1].first, F2 = b[b1].second;
    int F = fibo(l - b1 * BLOCK), S = -1;
    ans += F;
    if (ans >= 1000000009LL) ans -= 1000000009LL;
    ans += a[l];
    if (ans >= 1000000009LL) ans -= 1000000009LL;
    if ((b1 + 1) * BLOCK - 1 >= l + 1) {
      S = fibo(l + 1 - b1 * BLOCK);
      ans += S;
      if (ans >= 1000000009LL) ans -= 1000000009LL;
      ans += a[l + 1];
      if (ans >= 1000000009LL) ans -= 1000000009LL;
    }
    for (int i = l + 2; i < (b1 + 1) * BLOCK; i++) {
      int T = (F + S);
      if (T >= 1000000009LL) T -= 1000000009LL;
      ans += T;
      assert(T >= 0);
      if (ans >= 1000000009LL) ans -= 1000000009LL;
      ans += a[i];
      if (ans >= 1000000009LL) ans -= 1000000009LL;
      F = S;
      S = T;
    }
    for (int i = b1 + 1; i < b2; i++) {
      ans += sum[i];
      if (ans >= 1000000009LL) ans -= 1000000009LL;
    }
    F1 = b[b2].first, F2 = b[b2].second;
    F = F1, S = -1;
    ans += F;
    if (ans >= 1000000009LL) ans -= 1000000009LL;
    ans += (a[b2 * BLOCK]);
    if (ans >= 1000000009LL) ans -= 1000000009LL;
    if (r + 1 - b2 * BLOCK >= 2) {
      S = F2;
      ans += S;
      if (ans >= 1000000009LL) ans -= 1000000009LL;
      ans += (a[b2 * BLOCK + 1]);
      if (ans >= 1000000009LL) ans -= 1000000009LL;
    }
    for (int i = b2 * BLOCK + 2; i <= r; i++) {
      int T = (F + S);
      if (T >= 1000000009LL) T -= 1000000009LL;
      ans += T;
      if (ans >= 1000000009LL) ans -= 1000000009LL;
      ans += a[i];
      if (ans >= 1000000009LL) ans -= 1000000009LL;
      F = S;
      S = T;
    }
  }
  return ans;
}
void solve_case() {
  chrono::high_resolution_clock::time_point cur_start =
      chrono::high_resolution_clock::now();
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    sum[BL[i]] += a[i];
    if (sum[BL[i]] >= 1000000009LL) sum[BL[i]] -= 1000000009LL;
  }
  while (m--) {
    int t;
    int l, r;
    cin >> t >> l >> r;
    l--;
    r--;
    if (t == 1) {
      update(l, r);
    } else {
      cout << query(l, r) << '\n';
    }
  }
}
void precompute() {
  f[0] = 1;
  f[1] = 1;
  for (int i = 2; i < maxn + 2; i++)
    f[i] = (f[i - 1] + f[i - 2]) % 1000000009LL;
  for (int i = 0; i < maxn; i++) BL[i] = i / BLOCK;
}
int main() {
  ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  ;
  chrono::high_resolution_clock::time_point start =
      chrono::high_resolution_clock::now();
  precompute();
  int T = 1;
  cout << fixed << setprecision(10);
  for (int t = 1; t <= T; t++) {
    solve_case();
  }
  chrono::high_resolution_clock::time_point end =
      chrono::high_resolution_clock::now();
  long double time_spent =
      (chrono::duration_cast<chrono::duration<long double>>(end - start))
          .count();
  return 0;
}
