Elgoker locked the ship's treasure inside a secure safe. He encoded the master key as the constant term, $$$P(0)$$$, of a secret polynomial $$$P(x)$$$ of degree at most $$$k-1$$$. All calculations are heavily secured and evaluated modulo $$$10^{9}+7$$$.
To ensure the safe could be opened later, Elgoker distributed $$$k+2$$$ access codes to Chopper. Each access code is a coordinate pair $$$(x_{i}, y_{i})$$$, where $$$y_{i} = P(x_{i}) \pmod{10^{9}+7}$$$.
However, a mischievous monkey managed to infiltrate the ship and tampered with exactly one of the $$$k+2$$$ access codes, altering its $$$y_{i}$$$ value to a fake integer to lock everyone out. The remaining $$$k+1$$$ codes are completely untouched and lie perfectly on the original polynomial curve.
Given the $$$k+2$$$ access codes, your task is to help Chopper identify the corrupted code, discard it, and recover the master key $$$P(0) \pmod{10^{9}+7}$$$ so they can access the treasure!
The first line of the input contains a single integer $$$k$$$ ($$$2 \le k \le 2000$$$) indicating that Elgoker's secret polynomial $$$P(x)$$$ has a maximum degree of $$$k-1$$$.
The next $$$k+2$$$ lines each contain two integers $$$x_{i}$$$ and $$$y_{i}$$$ ($$$1 \le x_{i} \lt 10^{9}+7$$$, $$$0 \le y_{i} \lt 10^{9}+7$$$) — the $$$x$$$ and $$$y$$$ values of the $$$i$$$-th access code.
It is guaranteed that:
Print a single integer: the original master key $$$P(0) \pmod{10^{9}+7}$$$.
21 152 203 994 30
10
In the example, the threshold is $$$k=2$$$, meaning Elgoker's polynomial has a degree of at most 1 (it is a linear equation).
The true polynomial is $$$P(x)=5x+10 \pmod{10^{9}+7}$$$.
The actual valid access codes should be: $$$P(1)=15$$$, $$$P(2)=20$$$, $$$P(3)=25$$$, $$$P(4)=30$$$.
The third access code (3, 99) was tampered with by the monkey. After discarding it, the remaining valid codes (1, 15), (2, 20), and (4, 30) perfectly form the line $$$P(x)=5x+10$$$. The master key $$$P(0)$$$ is 10.
