CF1817C.Similar Polynomials

A polynomial $A(x)$ of degree $d$ is an expression of the form $A(x) = a_0 + a_1 x + a_2 x^2 + \dots + a_d x^d$, where $a_i$ are integers, and $a_d \neq 0$. Two polynomials $A(x)$ and $B(x)$ are called similar if there is an integer $s$ such that for any integer $x$ it holds that

$$B(x) \\equiv A(x+s) \\pmod{10^9+7}.$$

For two similar polynomials $A(x)$ and $B(x)$ of degree $d$, you're given their values in the points $x=0,1,\dots, d$ modulo $10^9+7$.

Find a value $s$ such that $B(x) \equiv A(x+s) \pmod{10^9+7}$ for all integers $x$.

一个次数为 $d$ 的多项式 $A(x)$ 是形如 $A(x) = a_0 + a_1 x + a_2 x^2 + \dots + a_d x^d$ 的表达式，其中 $a_i$ 为整数，且 $a_d \neq 0$。若存在整数 $s$，使得对任意整数 $x$ 均满足

$$B(x) \equiv A(x+s) \pmod{10^9+7},$$

则称两个多项式 $A(x)$ 和 $B(x)$ 是相似的。

现给定两个次数均为 $d$ 的相似多项式 $A(x)$ 和 $B(x)$ 在点 $x = 0, 1, \dots, d$ 处的取值（模 $10^9+7$ 意义下）。

请找出一个整数 $s$，使得对所有整数 $x$ 均满足

$$B(x) \equiv A(x+s) \pmod{10^9+7}.$$

The first line contains a single integer $d$ ($1 \le d \le 2\,500\,000$).

The second line contains $d+1$ integers $A(0), A(1), \ldots, A(d)$ ($0 \le A(i) \lt 10^9+7$) — the values of the polynomial $A(x)$.

The third line contains $d+1$ integers $B(0), B(1), \ldots, B(d)$ ($0 \le B(i) \lt 10^9+7$) — the values of the polynomial $B(x)$.

It is guaranteed that $A(x)$ and $B(x)$ are similar and that the leading coefficients (i.e., the coefficients in front of $x^d$) of $A(x)$ and $B(x)$ are not divisible by $10^9+7$.

第一行包含一个整数 $d$（$1 \le d \le 2\,500\,000$）。

第二行包含 $d+1$ 个整数 $A(0), A(1), \ldots, A(d)$（$0 \le A(i) \lt 10^9+7$）——多项式 $A(x)$ 的值。

第三行包含 $d+1$ 个整数 $B(0), B(1), \ldots, B(d)$（$0 \le B(i) \lt 10^9+7$）——多项式 $B(x)$ 的值。

保证 $A(x)$ 与 $B(x)$ 相似，且 $A(x)$ 与 $B(x)$ 的首项系数（即 $x^d$ 前的系数）均不能被 $10^9+7$ 整除。

Print a single integer $s$ ($0 \leq s \lt 10^9+7$) such that $B(x) \equiv A(x+s) \pmod{10^9+7}$ for all integers $x$.

If there are multiple solutions, print any.

输出一个整数 $s$（$0 \leq s \lt 10^9+7$），使得对所有整数 $x$，均有 $B(x) \equiv A(x+s) \pmod{10^9+7}$。

若存在多个解，输出任意一个即可。

In the first example, $A(x) \equiv x-1 \pmod{10^9+7}$ and $B(x)\equiv x+2 \pmod{10^9+7}$. They're similar because $$B(x) \equiv A(x+3) \pmod{10^9+7}.$$

In the second example, $A(x) \equiv (x+1)^2 \pmod{10^9+7}$ and $B(x) \equiv (x+10)^2 \pmod{10^9+7}$, hence $$B(x) \equiv A(x+9) \pmod{10^9+7}.$$

在第一个例子中，$A(x) \equiv x-1 \pmod{10^9+7}$ 且 $B(x)\equiv x+2 \pmod{10^9+7}$。它们是相似的，因为

$$B(x) \equiv A(x+3) \pmod{10^9+7}.$$

在第二个例子中，$A(x) \equiv (x+1)^2 \pmod{10^9+7}$ 且 $B(x) \equiv (x+10)^2 \pmod{10^9+7}$，因此

$$B(x) \equiv A(x+9) \pmod{10^9+7}.$$