#include <bits/stdc++.h>
using namespace std;
const long long c = 2000, inf = 2000000000ll;
long long a[c], first[c], n, m;
long long t, x, y, second;
long long mod = 1000000000ll;
int main() {
  ios_base::sync_with_stdio(0);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) cin >> a[i];
  first[0] = first[1] = 1ll;
  for (int i = 2; i <= n; i++) first[i] = (first[i - 1] + first[i - 2]) % mod;
  for (int i = 0; i < m; i++) {
    cin >> t >> x >> y;
    if (t == 1)
      a[x] = y;
    else {
      second = 0;
      for (int i = x; i <= y; i++)
        second = (second + (a[i] * first[i - x]) % mod) % mod;
      cout << second << endl;
    }
  }
  return 0;
}
