CF2159E Super-Short-Polynomial-San

这个问题在一些国家可能非常有名，但如果没有人出这样的问题，其他国家的人又如何了解它们呢？ —— [XXI Open Cup, Grand Prix of Tokyo](https://qoj.ac/problem/3091) 你将获得三个整数 $a,\ b,\ c$。 定义 $F(n)$ 为次数为 $2n$ 的如下多项式： $$ F(n) = (a x^2 + b x + c)^n $$ 你需要处理 $q$ 次如下类型的询问： - $n\;k$ ：请你计算 $\displaystyle \sum_{i=0}^{k} [x^i] F(n)$ 的值，结果对 $10^9+7$ 取模 $^{\ast}$。 但如果题目就这样结束，可能对你来说太简单了。于是有了一个小小的变数$^\dagger$：你需要在线地处理这些询问。 $^{\ast}$ 其中 $[x^a]F(n)$ 表示 $F(n)$ 的 $x^a$ 项的系数。 $^\dagger$ 希望加上这个变数后对你来说不会太难。连小孩子都知道怎么做，只不过你要再把这个方法快上 $8\,000\,000$ 倍。

第一行包含三个整数 $a$、$b$、$c$，满足 $1 \le a, b, c \le 10^9+6$。 第二行包含一个整数 $q$，表示询问次数，$1 \le q \le 3 \times 10^5$。 接下来 $q$ 行，每行两个整数 $n_i'$ 和 $k_i'$，表示第 $i$ 次询问的加密参数。 你需要按以下方式解密参数： - 令第 $i$ 次询问（答案对 $10^9+7$ 取模）的答案为 $ans_i$，其中 $ans_0=0$。 - 第 $i$ 次询问的 $n$ 和 $k$ 为 $n_i = n_i' \oplus ans_{i-1}$，$k_i = k_i' \oplus ans_{i-1}$，其中 $0 \le n_i \le 3\times 10^5$，$0 \le k_i \le 2n_i$。 注意全部 $n_i$ 之和与 $k_i$ 之和均无上界。

对于每个询问，输出一个整数，表示答案对 $10^9+7$ 取模的结果，每个答案占一行。

解密后的样例输入如下： ``` 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 ``` 在 OEIS 上，该多项式 $F(n)$ 可参见 [A084608](https://oeis.org/A084608)。不过不用去点那个链接，没什么特别有用的信息。相信我。 由 ChatGPT 5 翻译