#include <bits/stdc++.h>
using namespace std;
long long n, m, tr[400000 << 2], taga[400000 << 2], tagb[400000 << 2],
    s[400000], f[400000], pre[400000];
long long opt, x, y, ans[400000], bz[400000];
void Build(long long p, long long l, long long r) {
  if (l == r) {
    tr[p] = s[l];
    return;
  }
  long long ls = p * 2, rs = p * 2 + 1, mid = (l + r) / 2;
  Build(ls, l, mid);
  Build(rs, mid + 1, r);
  tr[p] = (tr[ls] + tr[rs]) % 1000000009;
  return;
}
void Pushdown(long long p, long long l, long long r) {
  if ((!taga[p]) && (!tagb[p])) return;
  long long ls = p * 2, rs = p * 2 + 1, mid = (l + r) / 2;
  long long a, b;
  a = taga[p];
  b = tagb[p];
  taga[ls] = (taga[ls] + a) % 1000000009;
  tagb[ls] = (tagb[ls] + b) % 1000000009;
  tr[ls] = (tr[ls] + b * f[mid - l + 2] + a * f[mid - l + 1] - b + 1000000009) %
           1000000009;
  long long tmpa = a, tmpb = b;
  a = (tmpa * f[mid - l] + tmpb * f[mid - l + 1]) % 1000000009;
  b = (tmpa * f[mid - l + 1] + tmpb * f[mid - l + 2]) % 1000000009;
  taga[rs] = (taga[rs] + a) % 1000000009;
  tagb[rs] = (tagb[rs] + b) % 1000000009;
  tr[rs] = (tr[rs] + b * f[r - (mid + 1) + 2] + a * f[r - (mid + 1) + 1] - b +
            1000000009) %
           1000000009;
  taga[p] = tagb[p] = 0;
  return;
}
void Modify(long long p, long long l, long long r, long long L, long long R) {
  if (L <= l && r <= R) {
    long long a = f[l - L + 1], b = f[l - L + 2];
    taga[p] = (taga[p] + a) % 1000000009;
    tagb[p] = (tagb[p] + b) % 1000000009;
    tr[p] = (tr[p] + b * f[r - l + 2] + a * f[r - l + 1] - b + 1000000009) %
            1000000009;
    return;
  }
  long long ls = p * 2, rs = p * 2 + 1, mid = (l + r) / 2;
  Pushdown(p, l, r);
  if (L <= mid) Modify(ls, l, mid, L, R);
  if (R > mid) Modify(rs, mid + 1, r, L, R);
  tr[p] = (tr[ls] + tr[rs]) % 1000000009;
  return;
}
long long Query(long long p, long long l, long long r, long long L,
                long long R) {
  if (L <= l && r <= R) return tr[p];
  long long Ans = 0, ls = p * 2, rs = p * 2 + 1, mid = (l + r) / 2;
  Pushdown(p, l, r);
  if (L <= mid) Ans = (Ans + Query(ls, l, mid, L, R)) % 1000000009;
  if (R > mid) Ans = (Ans + Query(rs, mid + 1, r, L, R)) % 1000000009;
  return Ans;
}
int main() {
  scanf("%lld%lld", &n, &m);
  for (long long i = 1; i <= n; i++) scanf("%lld", &s[i]);
  f[1] = f[2] = 1;
  for (long long i = 3; i <= n + 2; i++)
    f[i] = (f[i - 1] + f[i - 2]) % 1000000009;
  Build(1, 1, n);
  for (long long i = 1; i <= m; i++) {
    scanf("%lld%lld%lld", &opt, &x, &y);
    switch (opt) {
      case 1:
        Modify(1, 1, n, x, y);
        break;
      case 2:
        ans[++ans[0]] = Query(1, 1, n, x, y);
        break;
    }
  }
  for (long long i = 1; i <= ans[0]; i++) printf("%lld\n", ans[i]);
  return 0;
}
