L. Secret Polynomial
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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!

Input

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:

  • All $$$x_{i}$$$ are pairwise distinct.
  • Exactly one $$$y_{i}$$$ has been altered from its true value $$$P(x_{i}) \pmod{10^{9}+7}$$$.
  • The original polynomial $$$P(x)$$$ has degree $$$ \le k-1$$$.
Output

Print a single integer: the original master key $$$P(0) \pmod{10^{9}+7}$$$.

Example
Input
2
1 15
2 20
3 99
4 30
Output
10
Note

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.