WA on #14, RE on #15
玄关

#include<bits/stdc++.h>
using namespace std;
#define int long long 

#define DBG(x) DEBUG_print(#x, ':', x, '\n')
#define rep(i, a, b) for(int i = (a) ; i <= (b) ; i++)
#define per(i, a, b) for(int i = (b) ; i >= (a) ; i--)
#define MP make_pair
#define all(a) begin(a), end(a)
#define fi first
#define se second
typedef pair<int, int> P;

const int N = 2000000 + 10;
const int mod = 1e9 + 7;

int n, m, q;
string s;
int to[800000 + 5][100];
int step[800000 + 5][100];
int pre[800000 + 5];
P to_next(int idx){
    if(m < n){
        if(pre[idx + m] <= idx)
            return {idx % n + 1, 1};
        else
            return {(pre[idx + m] - 1) % n + 1, pre[idx + m] - idx};
    }
    else{
        int tmp = (m - n) / n % mod;
        int x = m % n;
        if(pre[idx + x] >= idx)
            return {(pre[idx + x] - 1) % n + 1, tmp * n % mod + pre[idx + x] + n - idx};
        if(pre[idx + x] == 0){
            if(pre[n] == 0)
                return {idx % n + 1, 1};
            return {pre[idx + x + n] - n, tmp * n % mod + pre[idx + x + n] - n - idx};
        }
        return {pre[idx + x], tmp * n % mod + pre[idx + x] - idx + n};
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin >> n >> m >> q;
    cin >> s;
    s = s + s;
    s = ' ' + s;
    for(int i = 1 ; i <= 2 * n ; i++){
        pre[i] = (s[i] == '1' ? i : pre[i - 1]);
    }
    rep(i, 1, n)
        to[i][0] = to_next(i).first, step[i][0] = to_next(i).second % mod;
    rep(k, 1, 62){
        rep(i, 1, n){
            to[i][k] = to[to[i][k - 1]][k - 1];
            step[i][k] = (step[i][k - 1] + step[to[i][k - 1]][k - 1]) % mod;
        }
    }
    while(q--){
        int s, k;
        cin >> s >> k;
        int previ = s % mod;
        s = (s - 1) % n + 1;
        int noww = s, ans = 0;
        per(l, 0, 62){
            if(k < (1ll << l))
                continue;
            k -= (1ll << l);
            ans += step[noww][l];
            ans %= mod;
            noww = to[noww][l];
        }
        cout << (ans + previ) % mod<< endl;
    }
    return 0;
}