This problem might be well-known in some countries, but how do other countries learn about such problems if nobody poses them?— XXI Open Cup, Grand Prix of Tokyo

You are given three integers $a,b,c$.

Let $F(n)$ be the polynomial of degree $2n$ defined as follows.

$$F(n)=\left ({a x^2+b x+c}\right) ^n$$

You are asked to solve $q$ queries of the following kind.

• $n\;k$: Please find the value of the sum $\displaystyle \sum_{i=0}^{k}{\left [ {x^i} \right] F(n)}$ modulo $10^9+7$$^{\text{∗}}$.

However, it might be too easy for you if this problem ends here. So here is a twist$^{\text{†}}$: You are asked to solve the queries online.

$^{\text{∗}}$Here, $[x^a]F(n)$ denotes the coefficient of $x^a$ of the polynomial $F(n)$.$^{\text{†}}$I hope it isn't too hard for you after the twist. Even a toddler knows one way to solve it. You just have to optimize that method by a factor of $8\,000\,000$.

Input

The first line contains three integers $a$, $b$, $c$ ($1 \le a,b,c \le 10^9+6$).

The second line contains the number of queries $q$ ($1 \le q \le 3 \cdot 10^5$).

Each of the $q$ following lines contains two integers $n_i'$ and $k_i'$ denoting the query in encrypted format.

You must decrypt the queries as follows.

• Let the answer to the $i$-th query modulo $10^9+7$ be $ans_i$. Here, $ans_0$ is defined to be $0$.
• Then, the values of $n$ and $k$ for the $i$-th query are $n_i = n_i' \oplus ans_{i-1}$ and $k_i = k_i' \oplus ans_{i-1}$ ($0 \le n_i \le 3\cdot 10^5$, $0 \le k_i \le 2n_i$).

Do note that both the sum of $n_i$ and the sum of $k_i$ over all queries are not bounded.

Output

For each query, print the answer modulo $10^9+7$ on a new line.

Note

The decrypted example input is as follows.

3 2 1
11
0 0
1 0
1 1
1 2
2 0
2 1
2 2
2 3
2 4
31415 9265
200000 69420

Here, the polynomial $F(n)$ corresponds to A084608 from OEIS. Don't worry about the link; there's nothing so useful there. Trust me.