L. Land of the Golden Butterflies
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The lord has vanished without a trace.

Inside a secluded castle, the royal family gathered to claim his inheritance. One by one, they perished—locked rooms, vanished alibis, headless corpses—until only two remained: Ange and Beatrice.

The lord's will was sealed within an epitaph. It was said that whoever deciphered it would become the rightful heir. Ange solved the riddle... but only a moment too late. At the end of the path, Beatrice was already waiting with a smile.

The inheritance is the family estate: a convex polygon within which stand two ancient landmarks. Yet Beatrice, in her magnanimity, offered Ange a chance to share the rule. The land will be divided by the following ritual:

  • A chord of the polygon is chosen uniformly at random. A chord is a straight line connecting two non-adjacent vertices of the polygon.
  • If at least one of the landmarks lies on the chord, or both landmarks fall on the same region after the partition, the chord is discarded and another is drawn.
  • Once a valid chord is found, the polygon is divided into two subregions.

Beatrice, having arrived first, always claims the larger half. Ange receives the smaller one.

Your task is to compute the expected difference in area between Beatrice's region and Ange's region.

Let $$$P = 10\,000\,000\,019$$$. P is a prime number. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{x}{y}$$$ where $$$x$$$ and $$$y$$$ are integers and $$$y \not\equiv 0 \pmod P$$$. Output the integer equal to $$$x\cdot y^{-1} \pmod P$$$. In other words, output such an integer $$$a$$$ that $$$0 \le a \lt P$$$ and $$$a\cdot y=x \pmod P$$$.

Input

The first line contains a single integer $$$N$$$ — the number of vertices of the polygon $$$(3 \leq N \leq 10^5)$$$.

Each of the next $$$N$$$ lines contains two integers $$$x_i, y_i$$$ $$$(-10^9 \leq x_i, y_i \leq 10^9)$$$, representing the coordinates of the polygon's vertices, given in clockwise order. The polygon is guaranteed to be convex , and no three consecutive vertices are collinear.

The last line contains four integers $$$x_p, y_p, x_q ,y_q$$$ $$$(-10^9 \leq x_p, y_p, x_q ,y_q \leq 10^9)$$$, representing the coordinates of the two landmarks, one at $$$(x_p,y_p)$$$ and another at $$$(x_q,y_q)$$$, which both are guaranteed to lie strictly inside the polygon.

Output

Print the answer modulo $$$10\,000\,000\,019$$$ in a single line. If it is impossible to select the chord to fit the criteria, print $$$-1$$$.

Examples
Input
7
0 0
-1 2
1 5
5 4
6 1
5 -1
2 -2
3 4 3 1
Output
11
Input
6
0 5
4 3
6 0
2 -1
0 0
-1 3
1 0 0 1
Output
5000000010
Input
3
10 0
0 0
5 10
3 1 7 3
Output
-1
Note

The polygon in the first test case can be visualized as follows:

Figure L.1: The polygon showing the two landmarks (inside points) and all chords that successfully separate them.

Depending on the language, the expected difference or other intermediate values can exceed the range of 32-bit or even 64-bit integers in worst cases. To avoid overflow:

  • C++: use __int128.
  • Java and Kotlin: use BigInteger from java.math.