题目背景

原题链接：https://oier.team/problems/89。

---

纷飞白雪零碎了异客的心，在无数的高山外，故人是否还在记忆的流水中，细嗅往年往月的百花？

只是他们在旧地的怀抱中，但有一个人却在海的那一端，潸然泪下……

人都有归属，只是某些人看不到罢了……

约定记号 $S^c$ 表示字符串 $S$ 循环 $c$ 次拼接而成的字符串。特别地，若 $c = \infty$，则表示字符串 $S$ 无限循环拼接而成的字符串。

题目描述

异客在一个无限循环的 $\texttt{01}$ 字符串 $T=S^\infty$ 上进行着他的旅程，其中 $S$ 的长度为 $n$，$T$ 的第 $i$ 个字符为 $T_i$。

异客的视野有限，只能看到后面 $m$ 个字符。

异客会进行 $q$ 次旅程，每次起点不同，移动次数也不同。

当异客在 $T_i$ 上时：

• 若 $T_{i+1\dots i+m}$ 中存在 $\texttt{1}$，则异客下一次会移动到其中最远的一个 $\texttt{1}$ 上。
• 否则，异客下一次会移动到下一个字符 $T_{i+1}$ 上。

你需要告诉异客，他会在哪里停下。由于答案会很大，你只需要告诉他对 $10^9+7$ 取模后的结果。

输入格式

第一行，三个正整数 $n,m,q$。

第二行，一个长度为 $n$ 的 $\texttt{01}$ 字符串 $S$。

接下来 $q$ 行，每行两个整数 $s, k$，表示起点在 $T_s$，移动 $k$ 次。

输出格式

$q$ 行，每行一个整数，表示停下的位置对 $10^9+7$ 取模后的值。

8 3 2
10001011
1 2
4 3

5
10

提示

【样例解释 #1】

$T$ 的前 $16$ 位为 $\texttt{1000101110001011}$。

第一次询问，位置移动为 $1 \to 2 \to 5$。

第二次询问，位置移动为 $4 \to 7 \to 9 \to 10$。

【样例 #2】

见附件中的 kingdom/kingdom2.in 与 kingdom/kingdom2.ans。

【样例 #3】

见附件中的 kingdom/kingdom3.in 与 kingdom/kingdom3.ans。

该组样例满足测试点 $5$ 的约束条件。

【样例 #4】

见附件中的 kingdom/kingdom4.in 与 kingdom/kingdom4.ans。

该组样例满足测试点 $9\sim 10$ 的约束条件。

【样例 #5】

见附件中的 kingdom/kingdom5.in 与 kingdom/kingdom5.ans。

该组样例满足测试点 $18\sim 20$ 的约束条件。

【数据范围】

对于所有测试数据，保证：$1 \le n \le 2 \times 10^{5}$，$1 \le m \le 10^{18}$，$1 \le q \le 2 \times 10^5$，$1 \le s \le 10^{18}$，$0 \le k \le 10^{18}$。

测试点编号	$n \le$	$m \le$	$q \le$	$s \le$	$k \le$	特殊性质
$1$	$2\times 10^5$	$10^9$	$2\times 10^5$	$10^9$	$0$	无
$2$		$10^{18}$		$10^{18}$
$3\sim 4$		$10^9$		$10^9$		$S$ 为 $\texttt{0}^n$ 或 $\texttt{1}^n$
$5$		$10^{18}$		$10^{18}$
$6\sim 8$	$10^2$	$n$	$10^2$	$n$	$10^2$	无
$9\sim 10$	$3\times 10^3$		$3\times 10^3$		$3\times 10^3$
$11\sim 12$	$2\times 10^5$	$n$	$2\times 10^5$		$1$
$13\sim 14$		$10^{18}$		$10^{18}$
$15\sim 17$		$10^9$		$10^9$
$18 \sim 20$		$10^{18}$		$10^{18}$