A FIFA egy meglepő szabályt hozott a labdarúgó-világbajnokság döntője előtt. A pályán a megszokott \(11\) játékos helyett minden csapatnak \(N\) játékosa tartózkodik, akik \(1\)-től \(N\)-ig terjedő számokkal vannak jelölve (a számok természetesen a mezükön láthatók).

A döntő már nagyban zajlik, és nagy az esélye annak, hogy Messi gólt lő. Amennyiben a pályára egy koordináta-rendszerként tekintünk, Messi koordinátája jelenleg \((0, 0)\), a \(k\) mezszámot viselő francia játékos koordinátája pedig \((x_k, y_k)\) (minden \(1 \leq k \leq N\)-re\()\).

Messi egy rendkívül intelligens játékos, de kevésbé ismert, hogy egy nagyszerű versenyprogramozó is egyben. Ezért megfigyeli az ellenfél játékosait, annak érdekében, hogy megtalálja a gyenge pontjukat.

A francia játékosok mind a \(2^N - 1\) nem üres részhalmazát megfigyeli. Az esélye meghatározásához meg kell tudnia hány olyan részhalmaz létezik, amelyekre érvényes, hogy a részhalmazt alkotó pontok konvex burka tartalmazza a \((0,0)\) pontot. Mivel ez a szám nagyon nagy is lehet, a \(10^9+7\)-tel történő osztás során kapott maradékot kell kiíratni.

Ez számára nem is okozna gondot, ha otthon ülne a számítógépe előtt, és a körzeti verseny feladatait oldaná, de mivel a labdarúgó-világbajnokság döntőjében játszik, kénytelen igénybe venni a segítségeteket.

Megjegyzés: az \(S\) pontok halmazának konvex burkát a következőképpen definiálhatjuk:

• ha az \(S\)-ben csak egy pont található, akkor a konvex burok pontosan ez a pont;
• ha az \(S\)-ben kollineáris pontok halmaza található (mindegyik pont ugyanazon az egyenesen), akkor a konvex burok a legrövidebb hossz, amely az összes pontot tartalmazza;
• ellenkező esetben, a konvex burok egy konvex sokszögу, amely az \(S\) részhalmaz minden pontját tartalmazza.

Úgy vesszük, hogy a konvex burok abban az esetben is tartalmazza a pontot, ha a pont a konvex burok valamely élén helyezkedik el.

A bemenet leírása

A szabványos bemenet első sora egy \(N\) egész számot tartalmaz, amely a pályán elhelyezkedő játékosok számát jelöli, az új szabály értelmében. A további \(N\) sor \(k\)-dik sorában két szám található: \(x_k\), \(y_k\), amelyek az ellenfél \(k\) mezszámú játékosának koordinátáit jelölik.

A kimenet leírása

A szabványos kimenet egyetlen sorában azon francia játékosok nem üres részhalmazának a számát kell elosztani \(10^9+7\)-tel, amelyeknek konvex burkában helyezkedik el Messi, és az így keletkező maradékot kell megjeleníteni.

1. példa

Bemenet

5
3 -1
8 -1
-9 1
7 -1
-4 1

Kimenet

9

A példa magyarázata

A játékosok megfelelő nem üres részhalmazai az alábbiak:

• \(\{1, 2, 3, 4, 5\}\)
• \(\{1, 2, 3, 5\}\)
• \(\{1, 2, 4, 5\}\)
• \(\{1, 2, 5\}\)
• \(\{1, 3, 4, 5\}\)
• \(\{1, 4, 5\}\)
• \(\{2, 3, 4, 5\}\)
• \(\{2, 3, 5\}\)
• \(\{3, 4, 5\}\)

2. példa

Bemenet

18
25 32
36 40
-13 7
-26 -49
3 27
-33 -39
-19 -9
36 6
-16 -31
-17 -48
-29 34
-49 36
-28 -25
7 37
2 45
-18 15
-23 -26
41 42

Kimenet

239247

Korlátozások

• \(1 \leq N \leq 10^5\).
• \(-10^9 \leq x_k, y_k \leq 10^9\), \(1 \leq k \leq N\)-re.
• \((x_k, y_k) \neq (x_j, y_j)\), \(1 \leq k < j \leq N\)-re.
• \((x_k, y_k) \neq (0, 0)\), \(1 \leq k \leq N\)-re.

A tesztpéldák öt diszjunkt csoportba vannak sorolva:

• A \(10\) pontot érő tesztpéldákban: \(N = 3\).
• A \(10\) pontot érő tesztpéldákban: \(y_1 = 1\) és \(y_k = -1\), \(1 < k \leq N\)-re.
• A \(25\) pontot érő tesztpéldákban: \(y_k \in \{-1, 1\}\), \(1 \leq k \leq N\)-re.
• A \(15\) pontot érő tesztpéldákban: \(N \leq 18\).
• A \(40\) pontot érő tesztpéldákban: nincsenek további korlátozások.