CFCF2159E.Super-Short-Polynomial-San

这个问题在一些国家可能非常有名，但如果没有人出这样的问题，其他国家的人又如何了解它们呢？

—— XXI Open Cup, Grand Prix of Tokyo

你将获得三个整数 $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。不过不用去点那个链接，没什么特别有用的信息。相信我。