Многочлен \(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\).
Выходные данные
Выведите одно целое число \(s\) (\(0 \leq s < 10^9+7\)) такое, что \(B(x) \equiv A(x+s) \pmod{10^9+7}\) для всех целых чисел \(x\).
Если существует несколько решений, выведите любое из них.
Примечание
В первом примере \(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}.\(\)
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1
1000000006 0
2 3
|
3
|
|
2
|
2
1 4 9
100 121 144
|
9
|