This time our child has a simple polygon. He has to find the number of ways to split the polygon into non-degenerate triangles, each way must satisfy the following requirements:

  * each vertex of each triangle is one of the polygon vertex; 
  * each side of the polygon must be the side of exactly one triangle; 
  * the area of intersection of every two triangles equals to zero, and the sum of all areas of triangles equals to the area of the polygon; 
  * each triangle must be completely inside the polygon; 
  * each side of each triangle must contain exactly two vertices of the polygon. 



The picture below depicts an example of a correct splitting.

<image>

Please, help the child. Calculate the described number of ways modulo 1000000007 (109 + 7) for him.

Input

The first line contains one integer n (3 ≤ n ≤ 200) — the number of vertices of the polygon. Then follow n lines, each line containing two integers. The i-th line contains xi, yi (|xi|, |yi| ≤ 107) — the i-th vertex of the polygon in clockwise or counterclockwise order.

It's guaranteed that the polygon is simple.

Output

Output the number of ways modulo 1000000007 (109 + 7).

Examples

Input

4
0 0
0 1
1 1
1 0


Output

2


Input

4
0 0
1 0
0 1
-1 0


Output

1


Input

5
0 0
1 0
1 1
0 1
-2 -1


Output

3

Note

In the first sample, there are two possible splittings:

<image>

In the second sample, there are only one possible splitting:

<image>
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.math.BigInteger;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author Vadim Semenov
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskC solver = new TaskC();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskC {
    private static final int MODULO = 1_000_000_007;
    public void solve(int testNumber, InputReader in, PrintWriter out) {
        int counter = in.nextInt();
        Point[] points = new Point[counter];
        for (int i = 0; i < counter; i++) points[i] = new Point(in.nextInt(), in.nextInt());
        boolean[][] diagonals = new boolean[counter][counter];
        // edges are diags too :)
        for (int i = 0; i < counter; i++)
            diagonals[(i + 1) % counter][i] = diagonals[i][(i + 1) % counter] = true;
        for (int i = 0; i < counter; i++) outer: for (int j = 0; j < i - 1; j++) {
            Point mid = points[i].add(points[j]).multiply(.5);
            if (!inside(mid, points)) continue outer;
            for (int k = 0; k < counter; k++) {
                if (k == i || k == j) continue;
                if (points[k].counterClockWise(points[i], points[j]) == 0) {
                    Point a = points[i].subtract(points[j]);
                    Point b = points[k].subtract(points[i]);
                    Point c = points[k].subtract(points[j]);
                    if (DoubleComparator.DEFAULT.compare(a.scalarProduct(b), 0) <= 0 &&
                            DoubleComparator.DEFAULT.compare(a.scalarProduct(c), 0) >= 0)
                        continue outer;
                }
                int l = (k + 1) % counter;
                if (l == i || l == j) continue;
                if (intersects(points[i], points[j], points[k], points[l])) continue outer;
            }
            diagonals[i][j] = diagonals[j][i] = true;
        }
        long[][] dp = new long[counter][counter];
        for (int second = 0; second < counter; second++) for (int first = second - 1; first >= 0; first--) {
            if (!diagonals[first][second]) continue;
            if (first == second - 1)
                dp[first][second] = 1;
            for (int third = first + 1; third < second; third++)
                if (diagonals[first][third] && diagonals[third][second])
                    dp[first][second] = (dp[first][second] + dp[first][third] * dp[third][second]) % MODULO;
        }
        out.println(dp[0][counter - 1]);
    }

    private boolean inside(Point point, Point[] polygon) {
        boolean inside = false;
        Point other = point.add(new Point(1_000_000_007, 1));
        for (int i = 0; i < polygon.length; i++) {
            if (intersects(point, other, polygon[i], polygon[(i + 1) % polygon.length]))
                inside = !inside;
        }
        return inside;
    }

    private boolean intersects(Point a, Point b, Point c, Point d) {
        return boundingBox(a, b, c, d) &&
                a.counterClockWise(b, c) * a.counterClockWise(b, d) <= 0 &&
                c.counterClockWise(d, a) * c.counterClockWise(d, b) <= 0;
    }

    private boolean boundingBox(Point a, Point b, Point c, Point d) {
        return checkBoundingBox(a.x, b.x, c.x, d.x) && checkBoundingBox(a.y, b.y, c.y, d.y);
    }

    private boolean checkBoundingBox(double a, double b, double c, double d) {
        if (a > b) { double t = a; a = b; b = t; }
        if (c > d) { double t = c; c = d; d = t; }
        return Math.max(a, c) <= Math.min(b, d);
    }
}

class InputReader {
    private final BufferedReader reader;
    private StringTokenizer tokenizer;

    public InputReader(InputStream in) {
        reader = new BufferedReader(new InputStreamReader(in));
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }

    public String next() {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(readLine());
        }
        return tokenizer.nextToken();
    }

    public String readLine() {
        String line = null;
        try {
            line = reader.readLine();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return line;
    }
}

class Point {
    public final double x, y;
    private DoubleComparator comparator = DoubleComparator.DEFAULT;

    public Point(double x, double y) {
        this.x = x;
        this.y = y;
    }

    public Point add(Point other) {
        return new Point(this.x + other.x, this.y + other.y);
    }

    public Point subtract(Point other) {
        return new Point(this.x - other.x, this.y - other.y);
    }

    public Point multiply(double mul) {
        return new Point(this.x * mul, this.y * mul);
    }

    public int counterClockWise(Point a, Point b) {
        a = a.subtract(this);
        b = b.subtract(this);
        return comparator.compare(a.vectorProduct(b), 0);
    }

    public double scalarProduct(Point other) {
        return this.x * other.x + this.y * other.y;
    }

    public double vectorProduct(Point other) {
        return this.x * other.y - this.y * other.x;
    }

    public int hashCode() {
        int result;
        long temp;
        temp = Double.doubleToLongBits(x);
        result = (int) (temp ^ (temp >>> 32));
        temp = Double.doubleToLongBits(y);
        result = 31 * result + (int) (temp ^ (temp >>> 32));
        return result;
    }

    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        Point point = (Point) o;

        if (comparator.compare(x, point.x) != 0) return false;
        if (comparator.compare(y, point.y) != 0) return false;

        return true;
    }

    public String toString() {
        return "(" + x + ", " + y + ")";
    }
}

interface DoubleComparator {
    public DoubleComparator DEFAULT = new DoubleComparator() {
        public static final double EPS = 1e-9;

        @Override
        public int compare(double first, double second) {
            if (first + EPS < second) return -1;
            if (first > second + EPS) return 1;
            return 0;
        }
    };

    public int compare(double first, double second);
}

