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.

Note

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

• If \(S\) only contains a single point, the convex hull is that point.
• If \(S\) is a set of pairwise collinear points, the convex hull is the shortest line segment containing all of them.
• Otherwise, the convex hull is the minimal-area convex polygon that contains all points in \(S\).

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

Input

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

Output

9

Explanation

The relevant subsets (1-indexed) are:

• \(\{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\}\)

Sample 2

Input

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

Output

239247

Constraints

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

Testcases are split into five disjoint groups:

• In tests worth 10 points: \(N = 3\).
• In tests worth 10 points: \(y_1 = 1\) и \(y_k = -1\), for \(1 < k \leq N\).
• In tests worth 25 points: \(y_k \in \{-1, 1\}\), for \(1 \leq k \leq N\).
• In tests worth 15 points: \(N \leq 18\).
• In tests worth 40 points: no additional constraints.