Students who use Android phones are certainly familiar with the pattern lock screen. An Android lock screen consists of a $3 \times 3$ grid of dots. By drawing a line on the screen to connect some of these dots, a lock pattern is formed. Three examples are shown below:

When drawing the line, several rules must be followed:

1. The number of connected dots must be at least 4. Connecting only two or three dots will result in an error.
2. The line between two dots cannot be curved.
3. Each dot can only be "used" once and cannot be repeated. Here, "used" means the finger has passed over the dot, and the dot turns green.
4. A line between two dots cannot "jump over" another dot unless that dot has already been "used".

For the last rule, refer to the explanation in the image below. The two diagrams on the left violate this rule; the two diagrams on the right (representing $2 \to 4 \to 1 \to 3 \to 6$ and $6 \to 5 \to 4 \to 1 \to 9 \to 2$) do not violate the rule because when "jumping over" a dot, that dot has already been "used".

Now, engineers want to improve the lock screen by increasing the number of dots and changing their positions. It is no longer a $3 \times 3$ grid, but the rules for drawing the lines remain the same.

Please calculate how many valid drawing patterns exist on the new lock screen.

Input

The first line contains an integer $n$, representing the number of dots. The next $n$ lines each contain two space-separated integers $x_i$ and $y_i$, representing the coordinates of each dot.

Output

Output a single line containing the number of valid patterns modulo $100000007$.

Examples

Input 1

4
0 0
1 1
2 2
3 3

Output 1

8

Note 1

Explanation: Assuming the 4 dots are numbered 1 to 4, the patterns are $1 \to 2 \to 3 \to 4$, $2 \to 1 \to 3 \to 4$, $3 \to 2 \to 1 \to 4$, $2 \to 3 \to 1 \to 4$, and their mirrors $4 \to 3 \to 2 \to 1$, $3 \to 4 \to 2 \to 1$, $2 \to 3 \to 4 \to 1$, $3 \to 2 \to 4 \to 1$.

Input 2

4
0 0
0 1
0 2
1 0

Output 2

18

Constraints

• For 30% of the data, $1 \le n \le 10$.
• For 100% of the data, $-1000 \le x_i, y_i \le 1000$, $1 \le n < 20$. All dot coordinates are distinct.