Traveler's Journey on Infinite 01 String

A traveler is journeying on an infinite binary string T defined as an infinite concatenation of a finite string S:

where the length of S is \(n\) and the \(i\)th character of T is \(T_i\). The traveler (called 异客) starts at a given position on T and makes a number of moves. However, his vision is limited: from any position \(i\), he can only see the next \(m\) characters \(T_{i+1}\) to \(T_{i+m}\>.

The moving rule is as follows:

• If there is at least one 1 in \(T_{i+1\dots i+m}\), he jumps to the position of the rightmost 1 within that window.
• If there is no 1 in the window, he moves just one step forward, i.e. to \(T_{i+1}\).

You are given \(q\) journeys. In each journey the traveler starts at a given position and makes a given number of moves. Since the answer may be huge, output the final position modulo \(10^9+7\).

Note on the infinite structure: Since \(T\) is defined as the infinite repetition of S, for any position \(i\) the corresponding character is \(S_{((i-1)\bmod n)+1}\) (we use 1-indexing throughout).

inputFormat

The first line contains three integers \(n\), \(m\), and \(q\) (\(1 \le n, m \le \) some limit, \(q \ge 1\)).

The second line contains a binary string S of length \(n\).

Then \(q\) lines follow. Each of these lines contains two integers: the starting position \(x\) and the number of moves \(k\) for that journey.

Notice: The starting position \(x\) can be any positive integer. Remember that the string T is infinite and periodic with period \(n\).

outputFormat

For each query, output a single line containing one integer: the final position (1-indexed) of the traveler modulo \(10^9+7\>.

sample

5 6 3
10100
4 6
2 10
7 4

6
9
8