E. Super-Short-Polynomial-Santime limit per test7 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard outputThis 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 TokyoYou 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$$$.InputThe 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.OutputFor each query, print the answer modulo $$$10^9+7$$$ on a new line.ExampleInput3 2 1110 00 10 02 14 63 07 713 1225 3131379 9237396176013 396306657Output1
1
3
6
1
5
15
27
36
396240845
819003547
NoteThe decrypted example input is as follows. 3 2 1110 01 01 11 22 02 12 22 32 431415 9265200000 69420Here, the polynomial $$$F(n)$$$ corresponds to A084608 from OEIS. Don't worry about the link; there's nothing so useful there. Trust me.