#include<iostream> #include<cstring> #include<ctime> #define timeMS (clock()*1000/CLOCKS_PER_SEC) using namespace std; #define int long long const int N=5000100,P=1000000007; inline int read(){ int i=getchar(),r=0; while(i<'0'||i>'9')i=getchar(); while(i>='0'&&i<='9')r=(r<<1)+(r<<3)+(i^48),i=getchar(); return r; } inline int fpow(int a,int b=P-2){ int c=1; for(;b;b>>=1,a=a*a%P)if(b&1)c=c*a%P; return c; } int n,q,opt,al,bl,ar,br,l,r,pow2[N],inv2[N]; int sump[2][N],sumi[2][N],f[N],g[N],sum0[N],sum1[N],h[N]; char s[N]; void init(){ pow2[0]=inv2[0]=1; pow2[1]=2;inv2[1]=fpow(2); for(int i=2;i<N;i++)pow2[i]=pow2[i-1]*pow2[1]%P,inv2[i]=inv2[i-1]*inv2[1]%P; cin>>n>>q>>opt; scanf("%s",s+1); for(int i=1;i<=n;i++){ sump[0][i]=sump[0][i-1]; sump[1][i]=sump[1][i-1]; sumi[0][i]=sumi[0][i-1]; sumi[1][i]=sumi[1][i-1]; sump[s[i]-'0'][i]=(sump[s[i]-'0'][i]+pow2[i])%P; sumi[s[i]-'0'][i]=(sumi[s[i]-'0'][i]+inv2[i])%P; sum0[i]=sum0[i-1]; sum1[i]=sum1[i-1]; if(s[i]==s[i-1])sum0[i]++; else sum1[i]++; } if(opt)al=read(),bl=read(),ar=read(),br=read(),l=read(),r=read(); for(int i=2;i<=n;i++){ f[i]=(f[i-1]+sump[s[i]-'0'][i-1]*inv2[i])%P;//sum0 pow2(i-j) g[i]=(g[i-1]+sumi[s[i]-'0'][i-1]*pow2[i])%P;//sum0 pow2(j-i) h[i]=(h[i-1]+sumi[(s[i]-'0')^1][i-1]*pow2[i])%P; } } inline void get_lr(){ l=(al*l+bl)%n+1; r=(ar*r+br)%n+1; if(l>r)swap(l,r); } inline int get_ans(int L,int R){ int ans1=(f[R]-f[L-1])%P; ans1=(ans1-sump[0][L-1]*(sumi[0][R]-sumi[0][L-1]))%P; ans1=(ans1-sump[1][L-1]*(sumi[1][R]-sumi[1][L-1]))%P; ans1=ans1*pow2[R-L]%P; int ans2=(g[R]-g[L-1]+h[R]-h[L-1]-2*(sum0[R]-sum0[L]+sum1[R]-sum1[L]))%P; ans2=(ans2-(pow2[R+1]-pow2[L])*(1-inv2[L-1]))%P; // ans2=(ans2-sumi[0][L-1]*(sump[0][R]-sump[0][L-1]))%P; // ans2=(ans2-sumi[1][L-1]*(sump[1][R]-sump[1][L-1]))%P; // ans2=(ans2-sumi[0][L-1]*(sump[1][R]-sump[1][L-1]))%P; // ans2=(ans2-sumi[1][L-1]*(sump[0][R]-sump[0][L-1]))%P; ans2=(inv2[2]*ans2+sum0[R]-sum0[L])%P; // cout<<ans1<<' '<<ans2<<endl; return (inv2[1]*(ans1+ans2)%P+P)%P; } signed main(){ // freopen("alternate.in","r",stdin); // freopen("alternate.out","w",stdout); init(); int ans=0; for(int t=1;t<=q;t++){ if(opt==1){ get_lr(); ans^=get_ans(l,r)+23*t; } else{ l=read(),r=read(); printf("%lld\n",get_ans(l,r)); } } if(opt==1)cout<<ans; // cerr<<timeMS; return 0; }