← 返回题目列表

Codeforces · 1817/C

C. 相似多项式

中文机器翻译题面 查看原题

次数 $$$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}.$$$$$$