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;
struct point {
  long long x, y;
  point() {}
  point(long long x, long long y) : x(x), y(y) {}
};
inline point toVec(const point &a, const point &b) {
  return point(b.x - a.x, b.y - a.y);
}
inline long long cross(const point &a, const point &b) {
  return a.x * b.y - a.y * b.x;
}
inline int orientation(const point &a, const point &b) {
  long long c = cross(a, b);
  if (c == 0) return 0;
  return c < 0 ? 1 : -1;
}
inline bool onSegment(const point &p, const point &q, const point &r) {
  if (orientation(toVec(p, q), toVec(p, r)) == 0 && q.x <= max(p.x, r.x) &&
      q.x >= min(p.x, r.x) && q.y <= max(p.y, r.y) && q.y >= min(p.y, r.y))
    return true;
  return false;
}
inline bool doIntersect(const point &p1, const point &q1, const point &p2,
                        const point &q2) {
  int o1 = orientation(toVec(p1, q1), toVec(p1, p2));
  int o2 = orientation(toVec(p1, q1), toVec(p1, q2));
  int o3 = orientation(toVec(p2, q2), toVec(p2, p1));
  int o4 = orientation(toVec(p2, q2), toVec(p2, q1));
  if (o1 != o2 && o3 != o4) return true;
  return false;
}
int n;
inline long long signedA2(vector<point> &pts) {
  long long S = 0;
  for (size_t i = 0; i < pts.size(); i++) {
    S += cross(pts[i], pts[(i + 1) % pts.size()]);
  }
  return S;
}
vector<point> pts;
bool ok[205][205];
long long memo[205][205];
long long dp(int b, int e) {
  if (memo[b][e] == -1) {
    if (e - b == 1)
      memo[b][e] = 1;
    else {
      memo[b][e] = 0;
      for (int k = b + 1; k < e; k++)
        if (ok[b][k] && ok[k][e]) {
          memo[b][e] = (memo[b][e] + dp(b, k) * dp(k, e)) % 1000000007;
        }
    }
  }
  return memo[b][e];
}
inline bool crossesPol(int i, int j) {
  for (int k = 0; k < n; k++) {
    if (i == k || j == k) continue;
    if (onSegment(pts[i], pts[k], pts[j])) {
      return true;
    }
    int w = (k + 1) % n;
    if (w == i || w == j) continue;
    if (doIntersect(pts[i], pts[j], pts[k], pts[w])) {
      return true;
    }
  }
  return false;
}
inline bool outsidePol(int i, int j) {
  int a = (i + n - 1) % n, b = (i + 1) % n;
  if (a == j || b == j) return false;
  point ia = toVec(pts[i], pts[a]), ib = toVec(pts[i], pts[b]),
        ij = toVec(pts[i], pts[j]);
  int ab = orientation(ia, ib), aj = orientation(ia, ij),
      bj = orientation(ib, ij);
  if (ab == 1)
    return aj < 0 || bj > 0;
  else if (ab <= 0)
    return aj < 0 && bj > 0;
  return false;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n;
  pts.assign(n, point());
  for (int i = 0; i < n; i++) {
    cin >> pts[i].x >> pts[i].y;
  }
  if (signedA2(pts) < 0) {
    reverse(pts.begin(), pts.end());
  }
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) ok[i][j] = 1;
  for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++)
      if (crossesPol(i, j)) ok[i][j] = 0;
  for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++)
      if (outsidePol(i, j)) ok[i][j] = 0;
  memset(memo, -1, sizeof memo);
  cout << dp(0, n - 1) << '\n';
}
