王国边缘

【题目背景】

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

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

人都有归属，只是某些人看不到罢了……约定记号 S^c 表示字符串 S 循环 c 次拼接而成的字符串。特别地，若 c = ∞，则表示字符串 S 无限循环拼接而成的字符串。

【题目描述】

异客在一个无限循环的 01 字符串 T=S^∞ 上进行着他的旅程，其中 SS 的长度为 n，T 的第 i 个字符为 Ti

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

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

当异客在 Ti 上时：若 Ti+1…i+m 中存在 1，则异客下一次会移动到其中最远的一个 1 上。否则，异客下一次会移动到下一个字符 Ti+1 上。你需要告诉异客，他会在哪里停下。由于答案会很大，你只需要告诉他对 10^9+7 取模后的结果。

【输入格式】

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

第二行，一个长度为 nn的 01 字符串 S。

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

【输出格式】

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

【样例输入】

8 3 2
10001011
1 2
4 3

【样例输出】

5
10

【样例说明】

样例 1 解释

T的前 16 位为 1000101110001011。

第一次询问，位置移动为 1→2→5。

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

大样例

【数据规模与约定】

对于所有测试数据，保证：1≤n≤2×10^5,1≤m≤10^18，1≤q≤2×10^5，1≤s≤10^18，0≤k≤10^18。

【来源】

在此键入。