fact[0]=1;
for(int i=1; i<fact.length; ++i)
    fact[i]=fact[i-1]*i%M;
int n=in.nextInt(), m=in.nextInt(), blockSize=(int)Math.sqrt(n), blocks=(n-1)/blockSize+1;
int[] a = new int[n], gInc = new int[blocks];
int[][] cnt = new int[45][blocks];
for(int i=0; i<n; ++i) {
    a[i]=in.nextInt();
    if(a[i]<45)
        ++cnt[a[i]][i/blockSize];
}
while(m-->0) {
    int qT=in.nextInt(), q1=in.nextInt(), q2=in.nextInt();
    if(qT==1) {
        --q1;
        --q2;
        int l=q1%blockSize, lB=q1/blockSize, r=q2%blockSize, rB=q2/blockSize;
        while(lB<rB||lB==rB&&l<=r) {
            if(l!=0||lB==rB) {
                int a1=a[lB*blockSize+l]+gInc[lB];
                if(a1<45)
                    --cnt[a1][lB];
                ++a[lB*blockSize+l];
                if(a1+1<45)
                    ++cnt[a1+1][lB];
                ++l;
                if(l>=blockSize) {
                    l=0;
                    ++lB;
                }
            } else {
                ++gInc[lB];
                for(int i=43; i>=1; --i)
                    cnt[i+1][lB]=cnt[i][lB];
                cnt[1][lB]=0;
                ++lB;
            }
        }
    } else if(qT==2) {
        long t=0;
        --q1;
        --q2;
        int l=q1%blockSize, lB=q1/blockSize, r=q2%blockSize, rB=q2/blockSize;
        while(lB<rB||lB==rB&&l<=r) {
            if(l!=0||lB==rB) {
                int a1=a[lB*blockSize+l]+gInc[lB];
                if(a1<45)
                    t+=fact[a1];
                ++l;
                if(l>=blockSize) {
                    l=0;
                    ++lB;
                }
            } else {
                for(int i=1; i<=44; ++i)
                    t+=fact[i]*cnt[i][lB];
                ++lB;
            }
        }
        out.println(t%M);
    } else {
        --q1;
        int block=q1/blockSize, a1=a[q1]+gInc[block];
        if(a1<45)
            --cnt[a1][block];
        a[q1]=q2-gInc[block];
        if(q2<45)
            ++cnt[q2][block];
    }
}