记录：https://www.luogu.com.cn/record/187634608

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define up(i,l,r) for(int i=l;i<=r;++i)
#define dn(i,l,r) for(int i=l;i>=r;--i)
const int mod=1e9+7;
const int N=2e5+5;
int n,m,q,nxt[N][62],lst[N];
char c[N];

int32_t main(){
	//freopen("kingdom2.in","r",stdin); 
//	freopen("my.txt","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin>>n>>m>>q;
	up(i,1,n) cin>>c[i];
	up(i,1,n) lst[i]=(c[i]=='1'?i:lst[i-1]);
	up(i,1,n){
		int res=n-i;
		if(m<=res){
			nxt[i][0]=max((int)1,lst[i+m]-i);
		}else{
			int k=m-res;
			int t=k/n;
			if(!t){
				if(lst[k]){
					nxt[i][0]=lst[k]+res;nxt[i][0]=max(nxt[i][0],(int)1); 
				}else{
					nxt[i][0]=max((int)1,lst[n]-i);
				}
			}else{
				int pmod=k%n;
				if(lst[pmod]){
					nxt[i][0]=lst[pmod]+res+t*n;nxt[i][0]=max(nxt[i][0],(int)1);
				}else{
					nxt[i][0]=max(nxt[i][0],max((int)1,lst[n]+(t-1)*n+res));
				}
			}
		}
	}
	up(j,1,60){
		up(i,1,n){
			nxt[i][j]=nxt[i][j-1];
			if((i+nxt[i][j-1])%n==0){
				nxt[i][j]=nxt[i][j]+nxt[n][j-1];
			}else{
				nxt[i][j]=nxt[i][j]+nxt[(i+nxt[i][j-1])%n][j-1];
			}
		}
	}
	while(q--){
		int s,k;
		cin>>s>>k;
		int ans=0,now=s;
		if(s%n==0) s=n;
		else s%=n;
		dn(i,60,0){
			if(k>>i&1){
				ans=(ans+nxt[s][i])%mod;
				s=s+nxt[s][i];
				if(s%n==0) s=n;
				else s=s%n; 
			}
		}
		cout<<(ans+now)%mod<<'\n'; 
	} 
	return 0;
}
//tomxi