#include<bits/stdc++.h> #define int long long #define endl '\n' using namespace std; const int maxn=5e6+7; const int mod=1e9+7; const int Inv2=(mod+1)>>1; bool ST; int n,q; bool opt; int Al,Ar,Bl,Br; bool a[maxn]; int P2[maxn],InvP2[maxn]; int nP2[maxn]; int rem[maxn]; int S[2][2][maxn]; int F[maxn]; int l[maxn],r[maxn]; int Ans[maxn]; bool ED; inline void Init_P2(){ P2[0]=InvP2[0]=1; for(int i=1;i<=n;i++)P2[i]=(P2[i-1]<<1)%mod,InvP2[i]=InvP2[i-1]*Inv2%mod; for(int i=2;i<=n;i++)nP2[i]=(nP2[i-1]+i*P2[i-2]%mod)%mod; } inline void Init_Arr(){ for(int i=1;i<=n;i++){ S[0][0][i]=(S[0][0][i-1]+(!a[i])*InvP2[i])%mod; S[0][1][i]=(S[0][1][i-1]+(a[i])*InvP2[i])%mod; S[1][0][i]=(S[1][0][i-1]+(!a[i])*P2[i])%mod; S[1][1][i]=(S[1][1][i-1]+(a[i])*P2[i])%mod; F[i]=(F[i-1]+InvP2[i]*S[1][a[i]][i-1]%mod)%mod; rem[i]=rem[i-1]+(a[i]==a[i+1]); } } inline void GetQ(){ if(opt){ cin>>Al>>Ar>>Bl>>Br>>l[0]>>r[0]; for(int i=1;i<=q;i++){ l[i]=(Al*l[i-1]+Bl)%n+1; r[i]=(Ar*r[i-1]+Br)%n+1; if(l[i]>r[i])swap(l[i],r[i]); } } else for(int i=1;i<=q;i++)cin>>l[i]>>r[i]; } inline void Print(){ if(opt){ int ans=0; for(int i=1;i<=q;i++)ans=ans^(Ans[i]+23*i)%mod; cout<<ans<<endl; } else for(int i=1;i<=q;i++)cout<<Ans[i]<<endl; cout.flush(); } signed main(){ios::sync_with_stdio(0);cin.tie(0); freopen("alternate.in","r",stdin); freopen("alternate.out","w",stdout); cin>>n>>q>>opt; for(int i=1;i<=n;i++){ char t;cin>>t;a[i]=t-'0'; } Init_P2();Init_Arr(); GetQ(); for(int i=1;i<=q;i++){ int L=l[i],R=r[i]; if(L==R){ Ans[i]=0; continue; } if(L+1==R){ Ans[i]=(a[L]==a[R]); continue; } int AP1=(F[R]-F[L-1]+mod)%mod; AP1=(AP1-(S[0][0][R]-S[0][0][L-1]+mod)%mod*S[1][0][L-1]+mod)%mod; AP1=(AP1-(S[0][1][R]-S[0][1][L-1]+mod)%mod*S[1][1][L-1]+mod)%mod; AP1=AP1*P2[R-L]%mod; int AP2=((P2[R-L-1]-1+mod)%mod*(R-L+1)%mod-nP2[R-L]+mod)%mod; AP2=(AP2+rem[R-1]-rem[L-1])%mod; Ans[i]=(AP1+AP2)%mod*Inv2%mod; } Print(); }