P11267

WA ON #13-20

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10,mod=1e9+7;
int n,m,q,mm;
char s[N];
queue<int> que;
int lst[N][70],lg[70];
int md[N][70];
signed main()
{
	scanf("%lld%lld%lld%s",&n,&m,&q,s+1);
	mm=m%n;
	for (int i=n;i>=1;i--){
		if (s[i]=='1'){
			que.push(n+i);
		}
	}
	for (int i=n;i>=1;i--){
		while (!que.empty()&&que.front()>i+mm){
			que.pop();
		}
		if (que.empty()){
			lst[i][0]=i%n+1;
			md[i][0]=1;
		}
		else{
			lst[i][0]=(que.front()-1)%n+1;
			md[i][0]=(que.front()+m/n*n-i)%mod;
		}
		if (s[i]=='1'){
			que.push(i);
		}
	}
	lg[0]=1;
	for (int i=1;i<=62;i++){
		lg[i]=lg[i-1]<<1;
	}
	for (int i=1;i<=62;i++){
		for (int j=1;j<=n;j++){
			lst[j][i]=lst[lst[j][i-1]][i-1];
			md[j][i]=(md[j][i-1]+md[lst[j][i-1]][i-1])%mod;
		}
	}
	while (q--){
		int x,k,ans;
		scanf("%lld%lld",&x,&k);
		ans=x%mod;
		x=(x-1)%n+1;
		for (int i=62;i>=0;i--){
			if (lg[i]<=k){
				ans=(ans+md[x][i])%mod;
				x=lst[x][i];
				k-=lg[i];
			}
		}
		printf("%lld\n",ans);
	}
	return 0;
}

@ PanShanxing