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) {}
  point operator+(const point &b) const { return point(x + b.x, y + b.y); }
  point operator-(const point &b) const { return point(x - b.x, y - b.y); }
};
inline long long cross(point a, point b) { return a.x * b.y - a.y * b.x; }
inline long long dot(point a, point b) { return a.x * b.x + a.y * b.y; }
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) {
  return (orientation(q - p, r - p) == 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));
}
inline bool intersect(const point &p1, const point &q1, const point &p2,
                      const point &q2) {
  int o1 = orientation(q1 - p1, p2 - p1);
  int o2 = orientation(q1 - p1, q2 - p1);
  int o3 = orientation(q2 - p2, p1 - p2);
  int o4 = orientation(q2 - p2, q1 - p2);
  if (o1 != o2 && o3 != o4) return true;
  if (onSegment(p1, p2, q1)) return true;
  if (onSegment(p1, q2, q1)) return true;
  if (onSegment(p2, p1, q2)) return true;
  if (onSegment(p2, q1, q2)) return true;
  return false;
}
inline long long signed2A(vector<point> &pol) {
  long long S = 0;
  for (int i = 0; i < (int)pol.size(); i++) {
    S += cross(pol[i], pol[(i + 1) % pol.size()]);
  }
  return S;
}
int N;
vector<point> pts;
bool ok[300][300];
long long memo[300][300];
vector<point> aux(3);
long long dp(int i, int j) {
  if (memo[i][j] == -1) {
    if (j - i <= 1)
      memo[i][j] = 1;
    else {
      memo[i][j] = 0;
      for (int k = i + 1; k < j; k++) {
        aux[0] = pts[i];
        aux[1] = pts[j];
        aux[2] = pts[k];
        if (ok[i][k] && ok[k][j] && signed2A(aux) < 0) {
          memo[i][j] += (dp(i, k) * dp(k, j)) % 1000000007;
          if (memo[i][j] >= 1000000007) memo[i][j] %= 1000000007;
        }
      }
    }
  }
  return memo[i][j];
}
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 (signed2A(pts) < 0) reverse(pts.begin(), pts.end());
  for (int i = 0; i < N; i++)
    for (int j = i + 1; j < N; j++) {
      ok[i][j] = 1;
      for (int k = 0; k < N && ok[i][j]; k++) {
        if (k == i || k == j) continue;
        int w = (k + 1) % N;
        if (w == i || w == j) continue;
        if (intersect(pts[i], pts[j], pts[k], pts[w])) ok[i][j] = 0;
      }
    }
  memset(memo, -1, sizeof memo);
  cout << dp(0, N - 1) << '\n';
}
