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.InputStreamReader;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.InputStream;

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

class TaskC {
    public void solve(int testNumber, FastScanner in, PrintWriter out) {
		n = in.nextInt();
		x = new int[n];
		y = new int[n];
		for (int i = 0; i < n; i++) {
			x[i] = in.nextInt();
			y[i] = in.nextInt();
		}
		if (signedArea() < 0) {
			for (int i = 0; i < n - i - 1; i++) {
				int j = n - i - 1;
				int t;
				t = x[i]; x[i] = x[j]; x[j] = t;
				t = y[i]; y[i] = y[j]; y[j] = t;
			}
		}
		long[][] d = new long[n][n];
		for (int dist = 1; dist < n; dist++) {
			for (int i = 0; i + dist < n; i++) {
				int j = i + dist;
				if (dist == 1) {
					d[i][j] = 1;
					continue;
				}
				for (int k = i + 1; k < j; k++) {
					if (triangleArea(i, k, j) > 0) {
						d[i][j] = (d[i][j] + d[i][k] * d[k][j]) % MOD;
					}
				}
			}
		}
		out.println(d[0][n - 1]);
    }

	final int MOD = 1000000007;
	int n;
	int[] x, y;

	private long signedArea() {
		long res = 0;
		for (int i = 0; i < n; i++) {
			int j = i + 1;
			if (j == n) {
				j = 0;
			}
			res += triangleArea(0, i, j);
		}
		return res;
	}

	private long triangleArea(int i, int j, int k) {
		int x12 = x[j] - x[i];
		int x13 = x[k] - x[i];
		int y12 = y[j] - y[i];
		int y13 = y[k] - y[i];
		return cross(x12, y12, x13, y13);
	}

	private long cross(long x1, long y1, long x2, long y2) {
		return x1*y2 - x2*y1;
	}
}

class FastScanner {

	private BufferedReader in;
	private StringTokenizer st;

	public FastScanner(InputStream stream) {
		in = new BufferedReader(new InputStreamReader(stream));
	}

	public String next() {
		while (st == null || !st.hasMoreTokens()) {
			try {
				st = new StringTokenizer(in.readLine());
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
		}
		return st.nextToken();
	}

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

}

