#include <bits/stdc++.h>
using namespace std;
const int maxN = 3e5 + 7;
const int mod = 1e9 + 9;
int N, M;
int arr[maxN];
int Mod(long long a) {
  a %= mod;
  a += mod;
  a %= mod;
  return a;
}
int f[maxN];
int CalcNext(int fir, int sec, int len) {
  if (len == 1) {
    return fir;
  }
  if (len == 2) {
    return sec;
  }
  return Mod(1ll * fir * f[len - 2] + 1ll * sec * f[len - 1]);
}
int CalcSum(int fir, int sec, int len) {
  if (len == 1) {
    return fir;
  }
  if (len == 2) {
    return Mod(fir + sec);
  }
  return Mod(CalcNext(fir, sec, len + 2) - sec);
}
struct Tree {
  int sum;
  int first, second;
} tree[maxN * 3];
void PushUp(int now) {
  tree[now].sum = Mod(tree[(now << 1)].sum + tree[(now << 1 | 1)].sum);
}
void Build(int now = 1, int left = 1, int right = N) {
  if (left == right) {
    tree[now].sum = arr[left];
    return;
  }
  Build((now << 1), left, ((left + right) >> 1));
  Build((now << 1 | 1), ((left + right) >> 1) + 1, right);
  PushUp(now);
}
void Down(int now, int left, int right, int add_first, int add_second) {
  tree[now].first = Mod(tree[now].first + add_first);
  tree[now].second = Mod(tree[now].second + add_second);
}
void Updata(int now_left, int now_right, int now = 1, int left = 1,
            int right = N) {
  if (right < now_left || now_right < left) {
    return;
  }
  tree[now].sum += CalcSum(f[(max(now_left, left) - now_left + 1)],
                           f[(max(now_left, left) - now_left + 1) + 1],
                           min(now_right, right) - max(now_left, left) + 1);
  tree[now].sum = Mod(tree[now].sum);
  if (now_left <= left && right <= now_right) {
    tree[now].first =
        Mod(tree[now].first + f[(max(now_left, left) - now_left + 1)]);
    tree[now].second =
        Mod(tree[now].second + f[(max(now_left, left) - now_left + 1) + 1]);
    return;
  }
  Updata(now_left, now_right, (now << 1), left, ((left + right) >> 1));
  Updata(now_left, now_right, (now << 1 | 1), ((left + right) >> 1) + 1, right);
}
int Query(int now_left, int now_right, int now = 1, int left = 1,
          int right = N) {
  if (right < now_left || now_right < left) {
    return 0;
  }
  if (now_left <= left && right <= now_right) {
    return tree[now].sum;
  }
  return Mod(
      CalcSum(CalcNext(tree[now].first, tree[now].second,
                       max(now_left, left) - left + 1),
              CalcNext(tree[now].first, tree[now].second,
                       max(now_left, left) - left + 2),
              min(now_right, right) - max(now_left, left) + 1) +
      Mod(Query(now_left, now_right, (now << 1), left, ((left + right) >> 1)) +
          Query(now_left, now_right, (now << 1 | 1), ((left + right) >> 1) + 1,
                right)));
}
int main() {
  scanf("%d%d", &N, &M);
  for (int i = 1; i <= N; ++i) {
    scanf("%d", &arr[i]);
  }
  Build();
  f[1] = f[2] = 1;
  for (int i = 3; i <= N + 2; ++i) {
    f[i] = Mod(f[i - 1] + f[i - 2]);
  }
  int op, left, right;
  for (int i = 1; i <= M; ++i) {
    scanf("%d%d%d", &op, &left, &right);
    if (op == 1) {
      Updata(left, right);
    }
    if (op == 2) {
      printf("%d\n", Query(left, right));
    }
  }
  return 0;
}
