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.BufferedReader;
import java.util.Comparator;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Collection;
import java.util.List;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.ArrayList;
import java.util.StringTokenizer;
import java.math.BigInteger;
import java.util.Collections;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author AlexFetisov
 */
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 boolean[][] goodSegment;

    public void solve(int testNumber, InputReader in, PrintWriter out) {
        int n = in.nextInt();
        Point[] p = new Point[n];
        for (int i = 0; i < n; ++i) {
            p[i] = new Point(in.nextInt() * 2, in.nextInt() * 2);
        }
        goodSegment = new boolean[n][n];
        for (int i = 0; i < n; ++i) {
            for (int j = i+1; j < n; ++j) {
                if (Math.abs(i - j) == 1 || (i == 0 && j == n-1)) {
                    goodSegment[i][j] = goodSegment[j][i] = true;
                    continue;
                }
                long S1 = sq(p, i, j);
                long S2 = sq(p, j, i);
                long S = sq(p);
                Point middle = new Point((p[i].x + p[j].x) / 2, (p[i].y + p[j].y) / 2);

                boolean good = inside(middle.x, middle.y, n, p);
                if (good) {
                    for (int k = 0; k < n; ++k) {
                        int k2 = k + 1;
                        if (k2 >= n) k2 -= n;
                        if (intersect(p[i], p[j], p[k], p[k2])) {
                            good = false;
                            break;
                        }
                    }
                }
                goodSegment[i][j] = goodSegment[j][i] = good;
            }
        }

        for (int i = 0; i < n; ++i) {
            int pp = (i - 1 + n) % n;
            int pn = (i + 1) % n;
            goodSegment[i][pp] = goodSegment[pp][i] = true;
            goodSegment[i][pn] = goodSegment[pn][i] = true;
        }

//        boolean[][] pCheck = petrCheck(p, n);
//        for (int i = 0; i < n; ++i) {
//            for (int j = 0; j < n; ++j) {
//                if (pCheck[i][j] != goodSegment[i][j]) {
//                    System.out.println("!!!" + i + " " + j);
//                }
//            }
//        }

        dp = new int[n][n];
        ArrayUtils.fill(dp, -1);
        out.println(rec(0, n-1));
    }

//    boolean[][] petrCheck(Point[] ps, int n) {
//        long[] x = new long[n];
//        long[] y = new long[n];
//        for (int i = 0; i < n; ++i) {
//            x[i] = ps[i].x;
//            y[i] = ps[i].y;
//        }
//        boolean[][] niceEdge = new boolean[n][n];
//        for (int i = 0; i < n; ++i) {
//            niceEdge[i][(i + 1) % n] = niceEdge[(i + 1) % n][i] = true;
//        }
//        for (int i = 0; i < n; ++i) {
//            outer: for (int j = i + 2; j < n; ++j) {
//                if ((j + 1) % n == i) continue;
//                long mx = (x[i] + x[j]) >> 1;
//                long my = (y[i] + y[j]) >> 1;
//                if (!inside(mx, my, n, ps)) continue;
//                long dx = x[j] - x[i];
//                long dy = y[j] - y[i];
//                for (int k = 0; k < n; ++k) if (k != i && k != j) {
//                    long dx1 = x[k] - x[i];
//                    long dy1 = y[k] - y[i];
//                    long dx2 = x[k] - x[j];
//                    long dy2 = y[k] - y[j];
//                    if (dx1 * dy - dy1 * dx == 0 && dx1 * dx + dy1 * dy >= 0 && dx2 * dx + dy2 * dy <= 0)
//                        continue outer;
//                    long sk = Long.signum(dx1 * dy - dy1 * dx);
//                    int l = k + 1;
//                    if (l >= n) l -= n;
//                    if (l != i && l != j) {
//                        long sl = Long.signum((x[l] - x[i]) * dy - (y[l] - y[i]) * dx);
//                        if (sk * sl == -1) {
//                            long si = Long.signum((x[i] - x[k]) * (y[l] - y[k]) - (y[i] - y[k]) * (x[l] - x[k]));
//                            long sj = Long.signum((x[j] - x[k]) * (y[l] - y[k]) - (y[j] - y[k]) * (x[l] - x[k]));
//                            if (si * sj == -1) {
//                                continue outer;
//                            }
//                        }
//                    }
//                }
//                niceEdge[i][j] = niceEdge[j][i] = true;
//            }
//        }
//        return niceEdge;
//    }

    private boolean inside(long mx, long my, int n, Point[] p) {
        boolean res = false;
        for (int i = 0; i < n; ++i) {
            long x1 = p[i].x;
            long y1 = p[i].y;
            long x2 = p[(i+1)%n].x;
            long y2 = p[(i+1)%n].y;
            if (y1 > y2) {
                long t = x1;
                x1 = x2;
                x2 = t;
                t = y1;
                y1 = y2;
                y2 = t;
            }
            if (y1 >= my || y2 < my) continue;
            long z = (x1 * (y2 - y1) + (x2 - x1) * (my - y1)) - mx * (y2 - y1);
            if (z == 0) return true;
            if (z > 0) res ^= true;
        }
        return res;
    }

    private boolean intersect(Point A, Point B, Point C, Point D) {
        if (onSeg(A, B, C) || onSeg(A, B, D) || onSeg(C, D, A) || onSeg(C, D, B)) {
            return true;
        }
        long v11 = C.sub(A).vProd(B.sub(A));
        long v12 = D.sub(A).vProd(B.sub(A));
        long v21 = A.sub(C).vProd(D.sub(C));
        long v22 = B.sub(C).vProd(D.sub(C));

        if (Long.signum(v11) * Long.signum(v12) < 0 && Long.signum(v21) * Long.signum(v22) < 0) {
            return true;
        }

        return false;
    }

    private boolean onSeg(Point A, Point B, Point C) {
        if (eq(A, C) || eq(B, C)) return false;
        if (B.sub(A).vProd(C.sub(A)) == 0) {
            long minX = Math.min(A.x, B.x);
            long minY = Math.min(A.y, B.y);
            long maxX = Math.max(A.x, B.x);
            long maxY = Math.max(A.y, B.y);
            return C.x >= minX && C.x <= maxX && C.y >= minY && C.y <= maxY;
        }
        return false;
    }

    private boolean eq(Point a, Point c) {
        return a.x == c.x && a.y == c.y;
    }

    long sq(Point[] p, int from, int to) {
        long S = 0;
        for (int i = from + 2; i != to; i = (i + 1) % p.length) {
            int prev = i - 1;
            int p1 = (i + p.length) % p.length;
            int p2 = (prev + p.length) % p.length;
            S += (p[p2].sub(p[from])).vProd(p[p1].sub(p[from]));
        }
        return Math.abs(S);
    }

    long sq(Point[] p) {
        long S = 0;
        for (int i = 2; i < p.length; ++i) {
            S += (p[i-1].sub(p[0])).vProd(p[i].sub(p[0]));
        }
        return Math.abs(S);
    }

    class Point {
        public long x, y;

        long vProd(Point p) {
            return x * p.y - y * p.x;
        }

        Point sub(Point p) {
            return new Point(x - p.x, y - p.y);
        }

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

    long rec(int le, int ri) {
        if (!goodSegment[le][ri]) return 0;
        if (le + 1 == ri) return 1;
        if (dp[le][ri] != -1) return dp[le][ri];
        long res = 0;
        for (int k = le + 1; k < ri; ++k) {
            res += (rec(le, k) * 1L * rec(k, ri)) % MOD;
            if (res >= MOD) res -= MOD;
        }
        dp[le][ri] = (int) res;
        return res;
    }

    final static int MOD = (int)1e9 + 7;
    int[][] dp;
}

class InputReader {
    private BufferedReader reader;
    private StringTokenizer stt;

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

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

    public String nextString() {
        while (stt == null || !stt.hasMoreTokens()) {
            stt = new StringTokenizer(nextLine());
        }
        return stt.nextToken();
    }

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

}

class ArrayUtils {

    public static void fill(int[][] f, int value) {
        for (int i = 0; i < f.length; ++i) {
            Arrays.fill(f[i], value);
        }
    }

}

