90 pts WA#3 #8 求调

#include <bits/stdc++.h>
#define cp make_pair
#define x first
#define y second
using namespace std;
const int N = 2e5+10, mod = 1e9+7;
int n,q,p; long long m,m1; int m2;
char a[N*3];
pair<int,long long> st[N][70];
long long s,t;
long long upd(long long a,long long b){
    return a+b>=mod ? a+b-mod : a+b;
}
signed main(){
    //freopen("kingdom5.in","r",stdin);
    freopen("kingdom.out","w",stdout);
    scanf("%d%lld%d",&n,&m,&q);
    scanf("%s",a+1);
    if(m>n) m2 = m % n +n, m1 = (m - m2)%mod;
    else m1 = 0, m2 = m;
    for(int i=1;i<=n;++i) a[i+n]=a[i];
    for(int i=1;i<=n;++i) a[i+n+n]=a[i];
    for(int i=1+1;i<=1+m2;++i) if(a[i]=='1') p=i;
    for(int i=1;i<=n;++i){
        if(a[i+m2]=='1') p=i+m2;
        if(p<=i) st[i][0]=cp(i+1,1);
        else st[i][0]=cp((p-1)%n+1,(m1+p-i)%mod);
    }
    //for(int i=1;i<=n;++i) cout<<"i: "<<i<<" "<<st[i][0].x<<" "<<st[i][0].y<<endl;
    for(int k=1;k<=63;++k){
        for(int i=1;i<=n;++i){
            long long y; int x;
            x = st[st[i][k-1].x][k-1].x;
            y = upd( st[st[i][k-1].x][k-1].y , st[i][k-1].y );
            st[i][k] = cp(x,y);
        }
    }
    long long ans;
    for(int i=1;i<=q;++i){
        scanf("%lld%lld",&s,&t);
        ans=s%mod; s=(s-1)%n+1;
        for(int k=63;k>=0;k--){
            if((t>>k)&1){
                ans = upd( ans , st[s][k].y );
                s = st[s][k].x;
            }
        }
        printf("%lld\n",ans);
    }
}