？萌妹求调

#include<bits/stdc++.h>
#define int __int128
#define F(i,a,b) for(int i=a;i<=b;i++)
#define R(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
const int N=2e5+7;
const int mod=1e9+7;
const int INF=1e18+7;
int n,m,q,f[N][65],num[N][65],bas2[N];
string s;
struct SGT{
	int val;
}t[N*4];
inline int fr(){
	int s=0,k=1;
	char ch=getchar();
	while(!isdigit(ch)){
		if(ch=='-') k=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		s=(s<<3)+(s<<1)+ch-'0';
		ch=getchar();
	}
	return s*k;
}
inline void fw(int x){
	if(x>9) fw(x/10);
	putchar((char)(x%10+'0'));
}
inline void pushup(int k){
	if(t[k<<1|1].val!=INF){
		t[k].val=t[k<<1|1].val;
	}
	else if(t[k<<1].val!=INF){
		t[k].val=t[k<<1].val;
	}
	else{
		t[k].val=INF;
	}
}
inline void update(int now_l,int now_r,int l,int r,int k,int q){
	if(l<=now_l&&r>=now_r){
		if(q==1){
			t[k].val=now_l;
		}
		else t[k].val=INF;
		return ;
	}
	int mid=(now_l+now_r)>>1;
	if(l<=mid) update(now_l,mid,l,r,k<<1,q);
	if(r>mid) update(mid+1,now_r,l,r,k<<1|1,q);
	pushup(k);
}
inline int query(int now_l,int now_r,int l,int r,int k){
	if(l<=now_l&&r>=now_r){
		return t[k].val;
	}
	int mid=(now_l+now_r)>>1,ans1=INF,ans2=INF;
	if(l<=mid) ans1=query(now_l,mid,l,r,k<<1);
	if(r>mid) ans2=query(mid+1,now_r,l,r,k<<1|1);
	pushup(k);
	if(ans2!=INF){
		return ans2;
	}
	else if(ans1!=INF){
		return ans1;
	}
	else return INF;
}
signed main(){
//	freopen("a.txt","r",stdin);
//	freopen("a.out","w",stdout);
	n=fr(),m=fr(),q=fr();
	cin>>s;
	s=" "+s;
	F(i,1,n*4){
		t[i].val=INF;
	}
	bas2[0]=1;
	F(i,1,65) bas2[i]=bas2[i-1]*2;
	F(i,1,n){
		update(1,n,i,i,1,s[i]-'0');
	} 
	F(i,1,n){
		int nw=(i+m)%n;
//		int k=m/n;
//		cout<<nw<<"\n";
		if(nw<=0) nw+=n;
		if(i+m>n){
			int id1=query(1,n,1,nw,1);
			int id2=query(1,n,i+1,n,1); 
			if(id1!=INF){
				f[i][0]=id1;
				
//				cout<<i<<" "<<id1<<" "<<"1\n";
				num[i][0]=id1+n-i+(m-n+i-nw);
			}
			else if(id2!=INF&&(id1==INF||id2-i>=id1+n-i)){
				f[i][0]=id2;
//				cout<<i<<" "<<id2<<" "<<"2\n";
				num[i][0]=id2-i+(m-nw+i-n);
			}
			else f[i][0]=(i+1)%n==0?1:(i+1)%n,num[i][0]=1;
		}
		else{
			int id=query(1,n,i+1,nw,1);
//			cout<<"id:"<<id<<"\n";
			if(id!=INF){
				num[i][0]=id-i;
			}
			else{
				id=i+1;
				num[i][0]=id-i;
			}
			f[i][0]=id;
		}
	}
	F(i,1,63){
		F(j,1,n){
			num[j][i]=num[j][i-1]+num[f[j][i-1]][i-1];
			num[j][i]%=mod;
			f[j][i]=f[f[j][i-1]][i-1];
//			cout<<num[j][i]<<" ";
//			if(f[f[j][i-1]][i-1]==0){
//				cerr<<j<<" "<<i<<"\n";
//			}
		}
//		cout<<"\n";
	}
//	cerr<<1<<"\n";
	F(b,1,q){
		int s,k;
		s=fr(),k=fr();
		if(!k){
			fw(s%mod);
			putchar('\n');
			continue;
		}
		int now=s,sum=now-(now%n==0?n:now%n);
		sum%=mod; 
		now=now%n==0?n:now%n;
		s=now;
		R(i,63,0){
//			cerr<<num[now][i]<<"\n";
			if((k&(bas2[i]))!=0){
//				if(b==1)
//				cerr<<now<<" "<<num[now][i]<<" "<<f[now][i]<<"\n"; 
				sum+=num[now][i];
				sum%=mod;
				now=f[now][i];
			}
		}
//		if((s%n+sum)==3000){
//			cerr<<s<<" "<<sum<<" "<<k<<" "<<b<<"\n";
//		} 
		fw((s+sum)%mod);
		putchar('\n');
	}
	return 0;
}
/*
5 7 3
01001

*/