310353: CF1818E. Similar Polynomials

E. Similar Polynomialstime limit per test4 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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

Input

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

Output

Print a single integer $s$ ($0 \leq s < 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.

ExamplesInput

1
1000000006 0
2 3

Output

3

Input

2
1 4 9
100 121 144

Output

9

Note

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) \) 和 \( B(x) \) 的度 \( d \) 以及它们在 \( x = 0, 1, \dots, d \) 处的值（模 \( 10^9+7 \)），求一个整数 \( s \) 使得对所有整数 \( x \)，都有 \( B(x) \equiv A(x+s) \pmod{10^9+7} \)。

输入数据格式：
- 第一行包含一个整数 \( d \) (\( 1 \le d \le 2,500,000 \))。
- 第二行包含 \( d+1 \) 个整数 \( A(0), A(1), \ldots, A(d) \) (\( 0 \le A(i) < 10^9+7 \))，表示多项式 \( A(x) \) 的值。
- 第三行包含 \( d+1 \) 个整数 \( B(0), B(1), \ldots, B(d) \) (\( 0 \le B(i) < 10^9+7 \))，表示多项式 \( B(x) \) 的值。

输出数据格式：
- 输出一个整数 \( s \) (\( 0 \leq s < 10^9+7 \))，满足 \( B(x) \equiv A(x+s) \pmod{10^9+7} \)。

注意：如果有多个解，输出任意一个即可。题目大意：给定两个相似的多项式 \( A(x) \) 和 \( B(x) \) 的度 \( d \) 以及它们在 \( x = 0, 1, \dots, d \) 处的值（模 \( 10^9+7 \)），求一个整数 \( s \) 使得对所有整数 \( x \)，都有 \( B(x) \equiv A(x+s) \pmod{10^9+7} \)。 输入数据格式： - 第一行包含一个整数 \( d \) (\( 1 \le d \le 2,500,000 \))。 - 第二行包含 \( d+1 \) 个整数 \( A(0), A(1), \ldots, A(d) \) (\( 0 \le A(i) < 10^9+7 \))，表示多项式 \( A(x) \) 的值。 - 第三行包含 \( d+1 \) 个整数 \( B(0), B(1), \ldots, B(d) \) (\( 0 \le B(i) < 10^9+7 \))，表示多项式 \( B(x) \) 的值。 输出数据格式： - 输出一个整数 \( s \) (\( 0 \leq s < 10^9+7 \))，满足 \( B(x) \equiv A(x+s) \pmod{10^9+7} \)。 注意：如果有多个解，输出任意一个即可。