#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define p_b push_back typedef long long ll; using namespace std; const int maxn=5e6+10,mod=1e9+7; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } int n,q,opt,pw[maxn],pwi[maxn],sm[maxn],sm2[maxn]; int sm0[maxn],sm0i[maxn],sm1[maxn],sm1i[maxn]; int f[maxn],g[maxn]; string s; int calc1(int l,int r){ int res=(sm2[r]-sm2[l-1]+mod)%mod; res=(res-sm0[l-1]*1ll*((sm0i[r]-sm0i[l-1]+mod)%mod)%mod+mod)%mod; res=(res-sm1[l-1]*1ll*((sm1i[r]-sm1i[l-1]+mod)%mod)%mod+mod)%mod; res=res*1ll*pw[r-l]%mod; return res; } int calc2(int l,int r){ int res=(f[r-l]*1ll*(r-l+1)%mod-g[r-l]+mod)%mod; (res+=sm[r]-sm[l])%=mod; return res; } int qry(int l,int r){ int s1=calc1(l,r),s2=calc2(l,r); //cout<<"! "<<s1<<" "<<s2<<endl; return (s1+s2)%mod*1ll*pwi[1]%mod; } void slv(){ n=read(),q=read(),opt=read(); pw[0]=pwi[0]=1;up(i,1,n)pw[i]=pw[i-1]*2%mod,pwi[i]=pwi[i-1]*1ll*((mod+1)/2)%mod; up(i,2,n)f[i]=(f[i-1]+pw[i-2])%mod,g[i]=(g[i-1]+pw[i-2]*1ll*i%mod)%mod; cin>>s,s=" "+s; up(i,2,n)sm[i]=sm[i-1]+(s[i]==s[i-1]); int S[2]={0,0}; up(i,1,n){ sm2[i]=(sm2[i-1]+S[s[i]-'0']*1ll*pwi[i]%mod)%mod; S[s[i]-'0']=(S[s[i]-'0']+pw[i])%mod; sm0[i]=sm0[i-1],sm0i[i]=sm0i[i-1],sm1[i]=sm1[i-1],sm1i[i]=sm1i[i-1]; if(s[i]=='0'){ (sm0[i]+=pw[i])%=mod,(sm0i[i]+=pwi[i])%=mod; }else { (sm1[i]+=pw[i])%=mod,(sm1i[i]+=pwi[i])%=mod; } } int al=0,bl=0,ar=0,br=0,l0=0,r0=0; if(opt)al=read(),bl=read(),ar=read(),br=read(),l0=read(),r0=read(); ll all=0; up(i,1,q){ int l=0,r=0; if(!opt)l=read(),r=read(); else { int f=(al*1ll*l0+bl)%n+1,g=(ar*1ll*r0+br)%n+1; if(f>g)swap(f,g); l0=l=f,r0=r=g; } int w=qry(l,r); if(!opt)printf("%d\n",qry(l,r)); else all^=(w+23*i); }if(opt)cout<<all; } int main(){ //freopen("alternate.in","r",stdin); //freopen("alternate.out","w",stdout); slv(); fclose(stdin); fclose(stdout); return 0; }