E. Super-Short-Polynomial-San
time limit per test
7 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
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.

Example
Input
3 2 1
11
0 0
0 1
0 0
2 1
4 6
3 0
7 7
13 12
25 31
31379 9237
396176013 396306657
Output
1
1
3
6
1
5
15
27
36
396240845
819003547
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.