#include <bits/stdc++.h>
using namespace std;
unsigned long long n, ans, f[10001], a[10001], m, i, l, r, x, type;
int main() {
  cin >> n >> m;
  f[0] = f[1] = 1;
  for (i = 2; i <= 10000; i++) f[i] = (f[i - 1] + f[i - 2]) % 1000000000;
  for (i = 1; i <= n; i++) cin >> a[i];
  while (m--) {
    cin >> type >> l >> r;
    ans = 0;
    if (type == 1)
      a[l] = r;
    else {
      for (x = 0; x <= r - l; x++) ans = (ans + f[x] * a[x + l]) % 1000000000;
      cout << ans << endl;
    };
  };
  return 0;
}
