rt

测评记录：here +第四个样例过不了

code:

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5*2+10,mod=1e9+7;
int stp[N][20],logn[N];
int n,m,T,st,k;
string s;
inline int query(int l,int r){
	if(r<l)	return 0;
	int lp=logn[r-l+1];
	return max(stp[l][lp],stp[r-(1<<lp)+1][lp]);
}
struct nodeskip{
	int to,val;//val: skip几步 
};
nodeskip stskip[N][62];
inline int read(){
	char c=getchar();
	int s=0,f=1;
	while(c<'0'||c>'9'){if(c=='-')	f=-1; c=getchar();}
	while(c>='0'&&c<='9'){s=s*10+c-'0';c=getchar();}
	return s*f;
}
inline void solve(){
	int rst=st,cnt=0,ans=0;
	if(st%n==0)	st=n;
	else st=st-(st/n)*n;
	while(k){
		if(k%2){
			ans=(ans+stskip[st][cnt].val)%mod;
			st=stskip[st][cnt].to;
		}
		cnt++;
		k/=2;
	}
	cout<<(rst%mod+ans%mod)%mod<<"\n";
}
signed main(){
//	freopen("kingdom4.in","r",stdin);
//	freopen("ans.txt","w",stdout);
	n=read();m=read();T=read();
	cin>>s;
	s=' '+s;
	for(int i=2;i<=n;i++) logn[i]=logn[i>>1]+1;
	for(int i=1;i<=n;i++)
		stp[i][0]=(s[i]=='1' ? i : 0);
	for(int j=1;j<=logn[n];j++){
		for(int i=1;i+(1<<j)<=n+1;i++){
			stp[i][j]=max(stp[i][j-1],stp[i+(1<<(j-1))][j-1]);
		}
	}
	int skp=0;	
	if(m>n){
		if(m%n==0){
			skp=((m/n-1)*n)%mod;
			m=n;
		}
		else{
			skp=((m/n)*n)%mod;
			m=m-(m/n)*n;
		}
	}
	for(int res=0,i=1;i<=n;i++){
		if(i+m>n){
			res=query(1,i+m-n);
			if(res){
				stskip[i][0].to=res;
				stskip[i][0].val=((res+n-i)%mod+skp)%mod;
				res=query(i+1,n);
			}
			else{
				if(!res){
					stskip[i][0].to=(i+1>n ? 1 : i+1);
					stskip[i][0].val=(1+skp)%mod;
				}
				else{
					stskip[i][0].to=res;
					stskip[i][0].val=((res-i)%mod+skp)%mod;
				}
			}
		}
		else{
			res=query(i+1,i+m);
			if(!res){
				stskip[i][0].to=(i+1>n ? 1 : i+1);
				stskip[i][0].val=(skp+1)%mod;
			}
			else{
				stskip[i][0].to=res;
				stskip[i][0].val=((res-i)+skp)%mod;
			}
		}
	}
	for(int j=1;j<=61;j++){
		for(int nto,i=1;i<=n;i++){
			nto=stskip[i][j-1].to;
			stskip[i][j].to=stskip[nto][j-1].to;
			stskip[i][j].val=(stskip[i][j-1].val+stskip[nto][j-1].val)%mod;
		}
	}//init
	while(T--){
		st=read();k=read();
		solve();
	}
	return 0;
}