【MX-S5-T1】王国边缘

原题链接：<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$ | $2\times 10^5$ | $10^{18}$ | $2\times 10^5$ | $10^{18}$ | $0$ | 无 | | $3\sim 4$ | $2\times 10^5$ | $10^9$ | $2\times 10^5$ | $10^9$ | $10^9$ | $S$ 为 $\texttt{0}^n$ 或 $\texttt{1}^n$ | | $5$ | $2\times 10^5$ | $10^{18}$ | $2\times 10^5$ | $10^{18}$ | $10^{18}$ | $S$ 为 $\texttt{0}^n$ 或 $\texttt{1}^n$ | | $6\sim 8$ | $10^2$ | $ n $ | $10^2$ | $n$ | $10^2$ | 无 | | $9\sim 10$ | $3\times 10^3$ | $ n $ | $3\times 10^3$ | $n$ | $3\times 10^3$ | 无 | | $11\sim 12$ | $2\times 10^5$ | $n$ | $2\times 10^5$ | $n$ | $1$ | 无 | | $13\sim 14$ | $2\times 10^5$ | $10^{18}$ | $2\times 10^5$ | $10^{18}$ | $1$ | 无 | | $15\sim 17$ | $2\times 10^5$ | $10^9$ | $2\times 10^5$ | $10^9$ | $10^9$ | 无 | | $18 \sim 20$ | $2\times 10^5$ | $10^{18}$ | $2\times 10^5$ | $10^{18}$ | $10^{18}$ | 无 |