C. Подобные многочлены
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Многочлен $$$A(x)$$$ степени $$$d$$$ — это выражение вида $$$A(x) = a_0 + a_1 x + a_2 x^2 + \dots + a_d x^d$$$, где $$$a_i$$$ — целые числа, и $$$a_d \neq 0$$$. Два многочлена $$$A(x)$$$ и $$$B(x)$$$ называются подобными, если существует целое число $$$s$$$, такое что для любого целого числа $$$x$$$ выполняется условие

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

Вам даны значения по модулю $$$10^9+7$$$ двух подобных многочленов $$$A(x)$$$ и $$$B(x)$$$ степени $$$d$$$ в точках $$$x=0,1,\dots, d$$$.

Найдите значение $$$s$$$, такое что $$$B(x) \equiv A(x+s) \pmod{10^9+7}$$$ для всех целых чисел $$$x$$$.

Входные данные

Первая строка содержит одно целое число $$$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)$$$ подобны, и что старшие коэффициенты (то есть коэффициенты перед $$$x^d$$$) многочленов $$$A(x)$$$ и $$$B(x)$$$ не делятся на $$$10^9+7$$$.

Выходные данные

Выведите одно целое число $$$s$$$ ($$$0 \leq s < 10^9+7$$$) такое, что $$$B(x) \equiv A(x+s) \pmod{10^9+7}$$$ для всех целых чисел $$$x$$$.

Если существует несколько решений, выведите любое из них.

Примеры
Входные данные
1
1000000006 0
2 3
Выходные данные
3
Входные данные
2
1 4 9
100 121 144
Выходные данные
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}.$$$$$$