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 NMAX = 222;
const int MOD = 1000000007;
int x[NMAX];
int y[NMAX];
int d[NMAX][NMAX];
bool good[NMAX][NMAX];
int sign(long long x) { return x == 0 ? 0 : (x > 0 ? 1 : -1); }
long long cross(long long x1, long long y1, long long x2, long long y2,
                long long x3, long long y3) {
  return (x1 * y2 + x2 * y3 + x3 * y1) - (y1 * x2 + y2 * x3 + y3 * x1);
}
bool linecross(long long x1, long long y1, long long x2, long long y2,
               long long x3, long long y3, long long x4, long long y4) {
  int ab =
      sign(cross(x1, y1, x2, y2, x3, y3)) * sign(cross(x1, y1, x2, y2, x4, y4));
  int cd =
      sign(cross(x3, y3, x4, y4, x1, y1)) * sign(cross(x3, y3, x4, y4, x2, y2));
  if (ab == 0 && cd == 0) {
    pair<int, int> a(x1, y1);
    pair<int, int> b(x2, y2);
    pair<int, int> c(x3, y3);
    pair<int, int> d(x4, y4);
    if (a > b) a.swap(b);
    if (c > d) c.swap(d);
    return a <= d && c <= b;
  }
  return ab <= 0 && cd <= 0;
}
int main() {
  int n, i, j, k, cnt, gap, mx, my;
  long long area, newarea;
  scanf("%d", &n);
  for (i = 0; i < n; i++) {
    scanf("%d%d", x + i, y + i);
    x[i] *= 2;
    y[i] *= 2;
  }
  area = 0;
  for (i = 0; i < n; i++) {
    area += cross(0, 0, x[i], y[i], x[(i + 1) % n], y[(i + 1) % n]);
  }
  if (area < 0) {
    area = -area;
    reverse(x, x + n);
    reverse(y, y + n);
  }
  for (i = 0; i < n; i++) {
    for (j = i + 1; j < n; j++) {
      for (k = 0; k < n; k++) {
        if (k == i || k == (i + n - 1) % n || k == j || k == j - 1) continue;
        if (linecross(x[i], y[i], x[j], y[j], x[k], y[k], x[(k + 1) % n],
                      y[(k + 1) % n]))
          break;
      }
      if (k < n) continue;
      newarea = 0;
      for (k = 0; k < i; k++) {
        newarea += cross(0, 0, x[k], y[k], x[(k + 1) % n], y[(k + 1) % n]);
      }
      newarea += cross(0, 0, x[i], y[i], x[j], y[j]);
      for (k = j; k < n; k++) {
        newarea += cross(0, 0, x[k], y[k], x[(k + 1) % n], y[(k + 1) % n]);
      }
      if (area < newarea || newarea < 0) continue;
      cnt = 0;
      for (k = 0; k < n; k++) {
        if (min(x[i], x[j]) <= x[k] && x[k] <= max(x[i], x[j]) &&
            min(y[i], y[j]) <= y[k] && y[k] <= max(y[i], y[j]) &&
            cross(x[i], y[i], x[j], y[j], x[k], y[k]) == 0) {
          cnt++;
        }
      }
      if (cnt != 2) continue;
      good[i][j] = true;
    }
  }
  for (i = 1; i < n; i++) {
    d[i - 1][i] = 1;
  }
  for (gap = 2; gap < n; gap++) {
    for (j = gap; j < n; j++) {
      i = j - gap;
      if (!good[i][j]) continue;
      for (k = i + 1; k < j; k++) {
        if (good[i][k] & good[k][j]) {
          d[i][j] += (long long)d[i][k] * d[k][j] % MOD;
          d[i][j] %= MOD;
        }
      }
    }
  }
  printf("%d", d[0][n - 1]);
  return 0;
}
