CF2159E Super-Short-Polynomial-San

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](https://qoj.ac/problem/3091) 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 $ .

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.

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

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](https://oeis.org/A084608) from OEIS. Don't worry about the link; there's nothing so useful there. Trust me.