#include <bits/stdc++.h>

using namespace std;

int mshri[2000000]={0};


     long factorial(long x)
    {
         if(x<2000000)
         if(mshri[x-1]!=0)return mshri[x-1];
         
         
        long ans=1;
        for (long i=(long)x;i>1;i--)
        {
            ans=ans*i;
        }
         
         if(x<2000000)
         mshri[x-1]=ans;
        return ans;
    }

int main() {
    
    int n;
    int m;
    cin >> n >> m;
    vector<int> A(n);
    for(int A_i = 0; A_i < n; A_i++){
       cin >> A[A_i];
    }
    for(int a0 = 0; a0 < m; a0++){
      
            int type,a,b;
            
            cin>>type>>a>>b;
            if (type==1)
            {
                for (int i=a-1;i<=b-1;i++)
                    A[i]=A[i]+1;
            }
            else if (type==2)
            {
                long sum=0;
                for (int i=a-1;i<=b-1;i++)
                {
                    sum=sum+factorial(A[i]);
                }
                
                sum=sum%1000000000;
                cout<<sum<<endl;
            }
            else
            {
                A[a-1]=(long)b;
            }
   
   }
     return 0;
    }