#include <stdio.h>

#include <string.h>

#include <string>

#include <math.h>

#include <stack>

#include <vector>

#include <algorithm>

using namespace std;

typedef long long LL;

const int N=1e5+;

const int mod=;

int q[][N<<],setval[N<<],add[N<<],mul[N<<];

void pushup(int rt){

    for(int i=;i<;++i)

      q[i][rt]=(q[i][rt<<]+q[i][rt<<|])%mod;

}

void downset(int rt,int c,int len){

    int a[];a[]=c;

    for(int i=;i<=;++i)

      a[i]=a[i-]*a[]%mod;

    for(int i=;i<;++i)

     q[i][rt]=a[i+]*len%mod;

    setval[rt]=c;

    add[rt]=;

    mul[rt]=;

}

void downadd(int rt,int c,int len){

    int a[];a[]=c;

    for(int i=;i<=;++i)

       a[i]=a[i-]*a[]%mod;

    q[][rt]=q[][rt]+a[]*len%mod+*a[]%mod*q[][rt]%mod+*a[]%mod*q[][rt]%mod;

    q[][rt]=q[][rt]+a[]*len%mod+*a[]%mod*q[][rt]%mod;

    q[][rt]=q[][rt]+a[]*len%mod;

    for(int i=;i<;++i)q[i][rt]%=mod;

    add[rt]=(add[rt]+c)%mod;

}

void downmul(int rt,int c,int len){

   int a[];a[]=c;

   for(int i=;i<=;++i)

    a[i]=a[i-]*a[]%mod;

   for(int i=;i<;++i)

    q[i][rt]=(q[i][rt]*a[i+])%mod;

   mul[rt]=(mul[rt]*c)%mod;

   add[rt]=(add[rt]*c)%mod;

}

void down(int rt,int l,int r){

    int m=(l+r)>>;

    if(setval[rt]!=-){

        downset(rt<<,setval[rt],m-l+);

        downset(rt<<|,setval[rt],r-m);

        setval[rt]=-;

    }

    if(mul[rt]!=){

        downmul(rt<<,mul[rt],m-l+);

        downmul(rt<<|,mul[rt],r-m);

        mul[rt]=;

    }

    if(add[rt]!=){

        downadd(rt<<,add[rt],m-l+);

        downadd(rt<<|,add[rt],r-m);

        add[rt]=;

    }

}

int op,c;

void modify(int rt,int l,int r,int x,int y){

    if(x<=l&&r<=y){

        if(op==)downadd(rt,c,r-l+);

        else if(op==)downmul(rt,c,r-l+);

        else downset(rt,c,r-l+);

        return;

    }

    int m=(l+r)>>;

    down(rt,l,r);

    if(x<=m)modify(rt<<,l,m,x,y);

    if(y>m)modify(rt<<|,m+,r,x,y);

    pushup(rt);

}

int ask(int rt,int l,int r,int x,int y){

    if(x<=l&&r<=y)return q[c-][rt];

    int ans=,m=(l+r)>>;

    down(rt,l,r);

    if(x<=m)ans=(ans+ask(rt<<,l,m,x,y))%mod;

    if(y>m)ans=(ans+ask(rt<<|,m+,r,x,y))%mod;

    return ans;

}

int main(){

    int n,m;

    while(~scanf("%d%d",&n,&m)){

        if(!n&&!m)break;

        for(int i=;i<=*n;++i){

            q[][i]=q[][i]=q[][i]=add[i]=;

            mul[i]=;

            setval[i]=-;

        }

        while(m--){

            int x,y;

            scanf("%d%d%d%d",&op,&x,&y,&c);

            if(op<=)modify(,,n,x,y);

            else printf("%d\n",ask(,,n,x,y));

        }

    }

    return ;

}