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^aF(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. Here, the polynomial (F(n)) corresponds to A084608 from OEIS. Don't worry about the link; there's nothing so useful there. Trust me.