题目背景

飞雪似絮，搅乱了心底藏着的万千波澜。隔着人海回望，你是否还在时光的褶皱里，细数着那年那月与我擦肩时的花香？

他们都困在各自的故事里安然，唯有我在思念的对岸，任由心事漫过眼帘。

爱本有归途，只是这份藏在尘埃里的惦念，你从未看见……

——江月诗.

题目描述

jiangys在一个无限循环的 $\texttt{01}$ 字符串 $T=S^\infty$ 上进行着他的旅程（$T=S^\infty$ 表示由 $\infty$ 个字符串拼接得到的字符串），其中 $S$ 的长度为 $n$，$T$ 的第 $i$ 个字符为 $T_i$。

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

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

当jiangys在 $T_i$ 上时：

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

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

输入格式

第一行，三个正整数 $n,m,q\ (1 \le n \le 2 \times 10^5,1 \le m \le 10^{18},1 \le q \le 2 \times 10^5)$。

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

接下来 $q$ 行，每行两个整数 $s, k$，表示起点在 $T_s$，移动 $k$ 次。($1 \le s \le 10^{18}$，$0 \le k \le 10^{18}$) 。

输出格式

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

输入样例

8 3 2
10001011
1 2
4 3

输出样例

5
10

说明/提示

【样例解释】

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

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

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