#include<bits/stdc++.h>
using namespace std; 
#define int long long
int xu[5005];
struct node{
	int l;
	int r;
	int sum;
	int tag;
};
node tp[500005];
void jianshu(int k,int l,int r){
	tp[k]=(node){l,r,0,0};
	if(l==r){
		tp[k].sum=xu[l];
		return;
	}
	int mid=(l+r)/2;
	jianshu(k<<1,l,mid);
	jianshu(k<<1|1,mid+1,r);
	tp[k].sum=tp[k<<1].sum+tp[k<<1|1].sum;
}
void pushdown(int x){
	if(tp[x].tag==0)return;
	tp[x<<1].sum+=(tp[x<<1].r-tp[x<<1].l+1)*tp[x].tag;
	tp[x<<1].tag+=tp[x].tag;
	tp[x<<1|1].sum+=(tp[x<<1|1].r-tp[x<<1|1].l+1)*tp[x].tag;
	tp[x<<1|1].tag+=tp[x].tag;
	tp[x].tag=0;
}
void add(int k,int l,int r,int a){
	if(tp[k].l>r || tp[k].r<l)return;
	if(tp[k].l>=l && tp[k].r<=r){
		tp[k].sum+=(tp[k].r-tp[k].l+1)*a;
		tp[k].tag+=a;
		pushdown(k);
		return;
	}
	pushdown(k);
	add(k<<1,l,r,a);
	add(k<<1|1,l,r,a);
	pushdown(k);
	tp[k].sum=tp[k<<1].sum+tp[k<<1|1].sum;
	
}
int cha(int k,int l,int r){
	pushdown(k);
	if(tp[k].l>r || tp[k].r<l)return 0;
	
	if(tp[k].l>=l && tp[k].r<=r){
		return tp[k].sum;
	}
	return cha(k<<1,l,r)+cha(k<<1|1,l,r);
}

signed main(){
	freopen("sjjgt.in","r",stdin);
	freopen("sjjgt.out","w",stdout);
    int n,m;
    cin>>n>>m;
    for(int i = 1;i<=n;i++)cin>>xu[i];
    jianshu(1,1,n);
    for(int j = 1;j<=m;j++){
        int op;
        cin>>op;
        if(op==1){
            int l,r,x;
            cin>>l>>r>>x;
            add(1,l,r,x);
        }
        else{
            int l,r,p;
            cin>>l>>r>>p;
            int a=cha(1,l,l),b=cha(1,r,r);
            int c=a;
            int ans=1;
            int t=b;
            while(b){
            	
            	if(b%2==1)ans*=c;
            	ans%=p;
            	
            	b=(b>>1);
            	c*=c;
                c%=p;
            }
            cout<<ans<<endl;
    	

            
        }
    }
	return 0;
}