Similar Polynomials

有两个次数为 $n$ 的多项式 $A,B$ 满足 $B(x) \equiv A(x+s) \pmod {10^9+7}$。给出它们在 $0, 1, 2, \dots, n$ 处的点值对 $10^9+7$ 取模的结果，求 $s \bmod 10^9+7$。 $n\le 2.5\times 10^6$。

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}. $ $ </p><p>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 $ .</p><p>Find a value $ s $ such that $ B(x) \\equiv A(x+s) \\pmod{10^9+7} $ for all integers $ x$$$.

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

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.

1
1000000006 0
2 3

3

2
1 4 9
100 121 144

9

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}. $ $ </p><p>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}. $ $$$