#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define fi first
#define se second
#define eb emplace_back
#define popc __builtin_popcount
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vp;
typedef unsigned long long ull;
typedef long double ld;

int read() {
    int x=0,w=1; char c=getchar(); 
    while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
    while(isdigit(c)) {x=x*10+c-'0'; c=getchar();}
    return x*w;
}

const int N=1e5+9,mod=1e9+9,Q=400000004,Q1=333333338;

int n,m,last;

int ksm(int x,int y,int res=1) {
    for(;y;y>>=1,x=1ll*x*x%mod) if(y%2==1) res=1ll*res*x%mod;
    return res;
}

namespace Pow {
    int b1[N],b2[N];
    void init() {
        b1[0]=1; rep(i,1,65536) b1[i]=1ll*b1[i-1]*Q%mod;
        b2[0]=1; rep(i,1,65536) b2[i]=1ll*b2[i-1]*b1[65536]%mod;
    }
    int ksm(int k) {
        return 1ll*b2[k>>16]*b1[k&65535]%mod;
    }
    int sum(int t,int len) {
        return 1ll*(mod-ksm(len)+1)*Q1%mod*t%mod;
    }
}
namespace SegT {
    int tot=1,ls[N*52],tag[N*52],s[N*52];
    void add(int p,int l,int r,int x) {
        tag[p]=x, s[p]=Pow::sum(x,r-l+1);
    }
    void pushdown(int p,int l,int r) {
        int mid=l+r>>1, tl=tag[p], tr=1ll*tl*Pow::ksm(mid-l+1)%mod;
        if(!ls[p]) ls[p]=++tot, ++tot;
        if(!tag[p]) return;
        add(ls[p],l,mid,tl), add(ls[p]+1,mid+1,r,tr), tag[p]=0;
    }
    void mdf(int p,int l,int r,int x,int y,int z) {
        if(l==x&&r==y) {add(p,l,r,z); return;}
        int mid=l+r>>1; pushdown(p,l,r);
        if(y<=mid) mdf(ls[p],l,mid,x,y,z);
        else if(x>mid) mdf(ls[p]+1,mid+1,r,x,y,z);
        else mdf(ls[p],l,mid,x,mid,z), mdf(ls[p]+1,mid+1,r,mid+1,y,1ll*z*Pow::ksm(mid-x+1)%mod);
        s[p]=(s[ls[p]]+s[ls[p]+1])%mod;
    }
    int qry(int p,int l,int r,int x,int y) {
        if(l==x&&r==y) return s[p];
        int mid=l+r>>1; pushdown(p,l,r);
        if(y<=mid) return qry(ls[p],l,mid,x,y);
        else if(x>mid) return qry(ls[p]+1,mid+1,r,x,y);
        else return (qry(ls[p],l,mid,x,mid)+qry(ls[p]+1,mid+1,r,mid+1,y))%mod;
    }
}

signed main() {
    n=read(), m=read();
    Pow::init();
    rep(i,1,m) {
        int tp=read(), l=read()^last, r=read()^last;
        if(tp==1) {
            int t=read(), p=read();
            t=1ll*t*Pow::ksm(p)%mod;
            SegT::mdf(1,1,n,l,r,t);
        } else {
            printf("%d\n",last=SegT::qry(1,1,n,l,r));
        }
    }
    return 0;
}