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>
const int mod = 1000000007;
struct P {
  int x, y;
};
int dp[210][210];
int perm[210][210];
P p[210];
int n;
P operator-(const P &a, const P &b) { return (P){b.x - a.x, b.y - a.y}; }
int operator==(const P &a, const P &b) { return a.x == b.x && a.y == b.y; }
P middle(const P &a, const P &b) {
  return (P){(a.x + b.x) / 2, (a.y + b.y) / 2};
}
long long det(const P &a, const P &b) {
  return (long long)a.x * b.y - (long long)a.y * b.x;
}
template <class T>
inline T abs(T x) {
  return x > 0 ? x : -x;
}
int sig(long long k) { return k ? k / abs(k) : 0; }
int online(P a, P b, P c) {
  int f = abs(c.x - a.x) + abs(b.x - c.x) == abs(b.x - a.x);
  f &= abs(c.y - a.y) + abs(b.y - c.y) == abs(b.y - a.y);
  return f;
}
int iscrs(P a, P b, P c, P d) {
  int abc = sig(det(b - a, c - a)), abd = sig(det(b - a, d - a));
  if (abc * abd == 1) {
    return 0;
  }
  if (abc == 0 && online(a, b, c) || abd == 0 && online(a, b, d)) {
    return 1;
  }
  if (abc * abd == 0) {
    return 0;
  }
  int cda = sig(det(d - c, a - c)), cdb = sig(det(d - c, b - c));
  if (cda == 0 && online(c, d, a) || cdb == 0 && online(c, d, b)) {
    return 1;
  }
  return cda * cdb == -1;
}
int inpoly(P a) {
  int res = 0;
  P tmp;
  for (int i = 0; i < n; i++) {
    P b = p[i] - a, c = p[i + 1] - a;
    if (b.y > c.y) {
      tmp = b;
      b = c;
      c = tmp;
    }
    if (b.y < 0 && c.y >= 0 && det(b, c) > 0) {
      res ^= 1;
      if (det(b, c) == 0) {
        return 1;
      }
    }
  }
  return res;
}
int f(int i, int j) {
  for (int k = 0; k < n; k++) {
    if (p[i] == p[k] || p[j] == p[k]) {
      continue;
    }
    if (det(p[k] - p[i], p[j] - p[i]) == 0 && online(p[i], p[j], p[k])) {
      return 0;
    }
    if (p[i] == p[k + 1] || p[j] == p[k + 1]) {
      continue;
    }
    if (iscrs(p[i], p[j], p[k], p[k + 1])) {
      return 0;
    }
  }
  return inpoly(middle(p[i], p[j]));
}
void add(int &t, int v) {
  t += v;
  if (t >= mod) t -= mod;
}
int count(int L, int R) {
  if (R - L <= 1) {
    return 1;
  }
  if (dp[L][R] != -1) {
    return dp[L][R];
  }
  int &res = dp[L][R];
  res = 0;
  if (!perm[L][R]) {
    return 0;
  }
  for (int i = L + 1; i < R; i++) {
    if (perm[L][i] && perm[i][R]) {
      int tmp = (long long)count(L, i) * count(i, R) % mod;
      add(res, tmp);
    }
  }
  return res;
}
int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    p[i] = (P){x * 2, y * 2};
  }
  p[n] = p[0];
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (i == j) continue;
      if (p[i] == p[j + 1] || p[i + 1] == p[j]) {
        perm[i][j] = 1;
      } else {
        perm[i][j] = f(i, j);
      }
    }
  }
  for (int i = 0; i <= n; i++) {
    for (int j = 0; j <= n; j++) {
      dp[i][j] = -1;
    }
  }
  printf("%d\n", count(0, n - 1));
  return 0;
}
