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

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$.

这个问题在某些国家可能早已广为人知，但如果没人将其提出，其他国家又怎能了解到这类问题呢？

— 第21届开放杯东京站大奖赛

给定三个整数 $a,b,c$。

定义次数为 $2n$ 的多项式 $F(n)$ 如下：

$$F(n)=\left ({a x^2+b x+c}\right) ^n$$

你需要回答 $q$ 个如下形式的查询：

• $n\;k$：请计算 $\displaystyle \sum_{i=0}^{k}{\left [ {x^i} \right] F(n)}$ 对 $10^9+7$ 取模的结果$^{\text{∗}}$。

然而，如果本题仅止步于此，对你而言或许过于简单。因此，这里有一个转折$^{\text{†}}$：你需要在线处理这些查询。

$^{\text{∗}}$此处，$[x^a]F(n)$ 表示多项式 $F(n)$ 中 $x^a$ 项的系数。

$^{\text{†}}$希望这个转折不会让你觉得太难。哪怕一个学步的幼儿都知道一种解法。你只需将该方法优化 $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.

第一行包含三个整数 $a$、$b$、$c$（$1 \le a,b,c \le 10^9+6$）。

第二行包含查询次数 $q$（$1 \le q \le 3 \cdot 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\cdot 10^5$，$0 \le k_i \le 2n_i$）。

请注意：所有查询的 $n_i$ 之和以及所有查询的 $k_i$ 之和均无上界限制。

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

对于每个查询，在新行中输出答案对 $10^9+7$ 取模的结果。

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 from OEIS. Don't worry about the link; there's nothing so useful there. Trust me.

解密后的示例输入如下：

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

此处，多项式 $F(n)$ 对应于 OEIS 中的序列 A084608。无需关注该链接；其中并无特别有用的信息。请相信我。