提交记录

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
int n,m,tmp,q,y,jump[70][N],d[70][N];
char st[N*3];
bool tag[N];
signed main(){
//	freopen("kingdom.in","r",stdin);
//	freopen("kingdom.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin>>n>>m>>q>>st+1;tmp=m;
	if(m>n) m=n+(m-1)%n+1,y=(tmp-m)%mod;
	for(int i=1;i<=n;i++) st[n+i]=st[n*2+i]=st[i];
	for(jump[0][1]=m+1;jump[0][1]>2;jump[0][1]--) if(st[jump[0][1]]=='1') break;
	for(int i=2;i<=n;i++){
		if(st[i+m]=='1')
			jump[0][i]=i+m;
		else
			jump[0][i]=max(jump[0][i-1],i+1),tag[i]=(jump[0][i-1]<=i);
	}
	for(int i=1;i<=n;i++){
		if(!tag[i]) d[0][i]=(y+(jump[0][i]-i))%mod;
		else d[0][i]=1;
		jump[0][i]=(jump[0][i]-1)%n+1;
	}
	for(int i=1;i<=69;i++){
		for(int j=1;j<=n;j++) jump[i][j]=jump[i-1][jump[i-1][j]],d[i][j]=(d[i-1][j]+d[i-1][jump[i-1][j]])%mod;
	}
	while(q--){
		int s,k,ans=0;
		cin>>s>>k;
		ans=s; s=(s-1)%n+1;
		for(int i=62;i>=0;i--){
			if(k>=(1ll<<i)) k-=(1ll<<i),(ans+=d[i][s])%=mod,s=jump[i][s];
		}
		cout<<ans<<'\n';
	}
	return 0;
}