次数 $$$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$$$,则两个多项式 $$$A(x)$$$ 和 $$$B(x)$$$ 被称为相似
$$$$$$ 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)$$$ 的值。
保证$$$A(x)$$$和$$$B(x)$$$相似,并且$$$A(x)$$$和$$$B(x)$$$的前导系数(即$$$x^d$$$前面的系数)不能被$$$10^9+7$$$整除。
输出
打印单个整数 $$$s$$$ ($$$0 \leq s < 10^9+7$$$),使得所有整数 $$$x$$$ 满足 $$$B(x) \equiv A(x+s) \pmod{10^9+7}$$$。
如果有多个解决方案,请打印其中一个。
示例
输入 #1
1 1000000006 0 2 3
输出 #1
3
输入 #2
2 1 4 9 100 121 144
输出 #2
9
注意
在第一个示例中,$$$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}.$$$$$$