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.util.*;
import java.io.*;
import java.math.*;

public class Main {
	FastScanner in;
	PrintWriter out;
	
	 int N = 205;
     long MOD = 1000000007;
    class point {
        long x, y;
        point() {}
        point(long _x, long _y) {
            x = _x;
            y = _y;
        }
        long cross(point c) {
            return x * c.y - y * c.x;
        }
        point dec(point c) {
            return new point(x - c.x, y - c.y);
        }
    }
    point p[] = new point[N], p2[] = new point[N];
    int n;
    long dp[][] = new long [N][N];
    
    long dfs (int l, int r) {
        if (dp[l][r] != -1)
            return dp[l][r];
     
        dp[l][r] = 0;
        if (r - l == 1)
            return dp[l][r] = 1;
     
        for (int i = l + 1; i < r; i++) {
            if ((p[l].dec(p[r]) ).cross((p[i].dec(p[r]) )) > 0)
                dp[l][r] = (dp[l][r] + dfs(l, i) * dfs(i, r)) % MOD;
        }
        return dp[l][r];
    }

	public void solve() throws IOException {
		n = in.nextInt();
		for (int i = 0; i < n+1; ++i) {
            for (int j = 0; j < n+1; ++j)
                dp[i][j] = -1;
		}
		for (int i = 0; i < n; ++i) {
            p[i] = new point();
            p[i].x = in.nextLong();
            p[i].y = in.nextLong();
		}
		long tmp = 0;
		p[n] = new point();
		p[n] = p[0];
		for (int i = 0; i < n; ++i) tmp += p[i].cross(p[i + 1]);
		if (tmp < 0) {
            for (int i = 0; i < n; ++i) {
                p2[i] = new point();
                p2[i] = p[n - i - 1];
            }
            for (int i = 0; i < n; ++i) {
                p[i] = p2[i];
            }
		}
		out.println(dfs(0, n - 1));
	}

	public void run() {
		try {
			in = new FastScanner();
			out = new PrintWriter(System.out);
			solve();
			out.close();
		} catch (IOException e) {
			e.printStackTrace();
		}
	}

	class FastScanner {
		BufferedReader br;
		StringTokenizer st;
		FastScanner() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			while (st == null || !st.hasMoreTokens()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
		long nextLong() {
			return Long.parseLong(next());
		}
		double nextDouble() {
			return Double.parseDouble(next());
		}
	}
	public static void main(String[] arg) {
		new Main().run();
	}
}