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>
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200, M = 1000000007;
int n, x[maxn], y[maxn], opt[maxn][maxn];
bool st[maxn][maxn];
int Muti(int p0, int p1, int q0, int q1) {
  int px = x[p1] - x[p0], py = y[p1] - y[p0], qx = x[q1] - x[q0],
      qy = y[q1] - y[q0];
  long long t = 1LL * px * qy - 1LL * py * qx;
  if (t > 0) return 1;
  if (t < 0) return -1;
  return 0;
}
int Poin(int p0, int p1, int q0, int q1) {
  int px = x[p1] - x[p0], py = y[p1] - y[p0], qx = x[q1] - x[q0],
      qy = y[q1] - y[q0];
  long long t = 1LL * px * qx + 1LL * py * qy;
  if (t > 0) return 1;
  if (t < 0) return -1;
  return 0;
}
bool Cross(int x, int y, int u, int v) {
  if (x == u || x == v || y == u || y == v) return 0;
  if (Muti(x, u, x, y) * Muti(x, v, x, y) < 0 &&
      Muti(u, x, u, v) * Muti(u, y, u, v) < 0)
    return 1;
  return 0;
}
bool Online(int p, int x, int y) {
  if (p == x || p == y) return 0;
  if (Muti(p, x, p, y) == 0 && Poin(p, x, p, y) < 0) return 1;
  return 0;
}
bool Outside(int p0, int p1) {
  int i, j = n - 1;
  double yi, yj, xi, xj, px = x[p0] + x[p1], py = y[p0] + y[p1];
  px = px / 2;
  py = py / 2;
  bool q = 1;
  for (i = 0; i < n; i++) {
    yi = y[i], yj = y[j], xi = x[i], xj = x[j];
    if (((yi < py && yj >= py) || (yj < py && yi >= py)) &&
        (xi <= px || xj <= px))
      q ^= (xi + (py - yi) / (yj - yi) * (xj - xi) < px);
    j = i;
  }
  return q;
}
bool Check(int x, int y) {
  if (x == y) return 0;
  if ((x + 1) % n == y || (y + 1) % n == x) return 1;
  for (int i = 0; i < n; i++)
    if (Online(i, x, y)) return 0;
  for (int i = 0; i < n; i++)
    if (Cross(x, y, i, (i + 1) % n)) return 0;
  if (Outside(x, y)) return 0;
  return 1;
}
int Ans(int x, int y) {
  if (opt[x][y] < 0) {
    opt[x][y] = 0;
    for (int i = x + 1; i < y; i++)
      if (st[x][i] && st[i][y])
        opt[x][y] = (1LL * Ans(x, i) * Ans(i, y) + opt[x][y]) % M;
  }
  return opt[x][y];
}
int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; i++) scanf("%d%d", &x[i], &y[i]);
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) {
      opt[i][j] = -1;
      st[i][j] = Check(i, j);
    }
  for (int i = 0; i < n - 1; i++) opt[i][i + 1] = 1;
  printf("%d\n", Ans(0, n - 1));
}
