Напомена: ово је незванична копија задатака. Као таква, не гарантује се да ће овај сајт бити одржаван, и немојте се изненадити ако са њега задаци одједном нестану.

FIFA introduced unexpected rules before the final of the World Cup. Instead of \(11\), each team now has \(N\) players, numbered from \(1\) to \(N\).

The finals are under way and Messi has an opportunity to score. Let us consider the field as a 2D plane, with Messi at \((0, 0)\), and the French players at \((x_k, y_k)\) (for \(1 \leq k \leq N\)).

Here’s little-known fact about Messi: he’s not only a very intelligent football player, but also an excellent competitive programmer. Because of this, he started examining about his opponents and looking for a weakness.

He is thinking about all \(2^N - 1\) non-empty subsets of the French team. To estimate the quality of his goal opportunity, he needs to know how many of them are such that the convex hull of the points in the subset contains \((0,0)\). Since this number can be very large, you should print its remainder modulo \(10^9 + 7\).

This wouldn’t be a issue if he was at home with a computer, solving the Serbian qualifiers to get to the county-level competition, but since he is in the World Cup finals, he needs your help.


The convex hull of a set of points \(S\) is defined as follows:

If a point is on the perimeter of the convex hull, we consider it to be contained in the hull.

Input format

The first line of standard input contains an integer \(N\), the number of players in a team (according to the new rules).

The following \(N\) lines contain two integers each. The \(k\)-th line contains \(x_k, y_k\): the coordinates of the \(k\)-th French player.

Output format

Your program should print one line to the standard output: the number of non-empty sets of French players for which the convex hull contains Messi, modulo \(10^9 + 7\).

Sample 1


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




The relevant subsets (1-indexed) are:

Sample 2


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




Testcases are split into five disjoint groups: