90 pts WA on #14 #15求条

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//	取模之前要减去1，以防模为0
ll f[80][400010];
ll g[80][400010];
ll a[400010];
ll n, m, q;
char c[300010];
const ll mod = 1e9 + 7;
int t, last;

int main() {
//	freopen("kingdom5.in", "r", stdin);
//	freopen("kingdom5.out", "w", stdout);
	scanf("%lld%lld%lld", &n, &m, &q);
	scanf("%s", c + 1);
//	puts("R");
	bool flag = false;
	for (int i = 1; i <= n; i++)
		if (c[i] == '1')
			last = i, flag = true;
	for (int i = 1; i <= n; i++) {
		if (c[i] == '1')
			last = i;
		a[i] = last;
	}
	if (flag) {
		for (int i = 1; i <= n; i++) {
			if (i + m <= n) {
				if (a[i + m] > i) {
					f[0][i] = a[i + m];
					g[0][i] = a[i + m] - i;

				} else {
					f[0][i] = i % n + 1;
					g[0][i] = 1;
				}
			} else {
				ll x = (i + m - 1) % n + 1;
				if (m >= n) {
					f[0][i] = a[x];
					ll temp = (i + m - 1) / n; //所在位置的循环节
					g[0][i] = f[0][i] - i + temp * n;

				} else {
					ll s = a[x];
					if (s > i || s <= x) {
						f[0][i] = a[x];
						if (s > i)
							g[0][i] = f[0][i] - i;
						else
							g[0][i] = f[0][i] + n - i;
					} else {
						f[0][i] = i % n + 1;
						g[0][i] = 1;
					}
				}
			}
		}
	} else {
//		puts("R");
		for (int i = 1; i <= n; i++) {
			f[0][i] = (i - 1) % n + 1;
			g[0][i] = 1;
		}
	}
	for (int i = 1; i <= 62; i++) {
		for (int j = 1; j <= n; j++) {
			f[i][j] = f[i - 1][f[i - 1][j]];
			g[i][j] = (g[i - 1][j] + g[i - 1][f[i - 1][j]]) % mod;
		}
	}
	while (q--) {
		ll x, y;
		scanf("%lld%lld", &x, &y);
		ll ans = 0;
		t = x % mod;
		if (y == 0) {
			ans = x;
			printf("%lld\n", ans % mod);
		} else {
			x = (x - 1) % n + 1; //在每组里的相对位置
			for (int i = 62; i >= 0; i--) {
				if (y & (1ll << i)) {
					ans = (ans + g[i][x]) % mod;
					x = f[i][x];
					y ^= (1ll << i);
				}
			}
			printf("%lld\n", (ans % mod + t) % mod);
		}


	}
	return 0;
}