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;
double pi = 2 * acos(0);
class Vector {
 public:
  double x, y;
  Vector(double _x = 0, double _y = 0) {
    x = _x;
    y = _y;
  }
  Vector operator+(Vector a) const { return Vector(x + a.x, y + a.y); }
  Vector operator+=(Vector a) { return *this = *this + a; }
  Vector operator-(Vector a) const { return Vector(x - a.x, y - a.y); }
  Vector operator-=(Vector a) { return *this = *this - a; }
  Vector operator*(double p) const { return Vector(x * p, y * p); }
  Vector operator*=(double p) { return *this = *this * p; }
  bool operator<(const Vector a) const {
    if (x == a.x) return y < a.y;
    return x < a.x;
  }
  double len() const { return sqrt(x * x + y * y); }
  double angle() const { return atan2(x, y); }
};
double EQ(double a, double b) { return abs(a - b) < 1e-11; }
struct LineEQ {
  double a, b, c;
};
double len(Vector a) { return sqrt(a.x * a.x + a.y * a.y); }
double cross(Vector a, Vector b) { return a.x * b.y - a.y * b.x; }
double scalar(Vector a, Vector b) { return a.x * b.x + a.y * b.y; }
bool parallel(pair<Vector, Vector> a, pair<Vector, Vector> b) {
  return abs(cross(a.first - a.second, b.first - b.second)) < 1e-11;
}
Vector lineline(pair<Vector, Vector> a, pair<Vector, Vector> b) {
  double x1 = a.first.x, y1 = a.first.y, x2 = a.second.x, y2 = a.second.y,
         x3 = b.first.x, y3 = b.first.y, x4 = b.second.x, y4 = b.second.y;
  double den = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4);
  return Vector(
      ((x1 * y2 - y1 * x2) * (x3 - x4) - (x1 - x2) * (x3 * y4 - y3 * x4)) / den,
      ((x1 * y2 - y1 * x2) * (y3 - y4) - (y1 - y2) * (x3 * y4 - y3 * x4)) /
          den);
}
bool onSegment(pair<Vector, Vector> l, Vector v) {
  int endpoints = 1;
  bool ok1, ok2;
  if (l.first.x > l.second.x) swap(l.first, l.second);
  ok1 = l.first.x - endpoints * 1e-11 < v.x &&
        v.x - endpoints * 1e-11 < l.second.x;
  if (l.first.y > l.second.y) swap(l.first, l.second);
  ok2 = l.first.y - endpoints * 1e-11 < v.y &&
        v.y - endpoints * 1e-11 < l.second.y;
  return ok1 && ok2;
}
bool segmentsegment(pair<Vector, Vector> a, pair<Vector, Vector> b) {
  if (parallel(a, b)) return false;
  Vector i = lineline(a, b);
  return onSegment(a, i) && onSegment(b, i);
}
int n;
Vector point[222];
bool inside[222][222];
int next(int a) {
  a += 1;
  return a == n ? 0 : a;
}
int dp[222][222];
int solve(int a, int b) {
  if (next(a) == b) return 1;
  if (dp[a][b] != -1) return dp[a][b];
  int ans = 0;
  for (int i = next(a); i != b; i = next(i)) {
    if ((inside[a][i] || i == next(a)) && (inside[b][i] || next(i) == b)) {
      ans = (ans + (long long)solve(a, i) * solve(i, b)) % 1000000007;
    }
  }
  return dp[a][b] = ans;
}
bool inside_polygon(Vector p) {
  double angle = 0.0;
  for (int i = 0; i < n; i++) {
    double a = (point[next(i)] - p).angle();
    a -= (point[i] - p).angle();
    if (a < -pi) a += 2.0 * pi;
    if (a > pi) a -= 2.0 * pi;
    if (EQ(p.x, point[i].x) && EQ(p.y, point[i].y)) return false;
    if (EQ(abs(abs(a) - pi), 0)) return false;
    angle += a;
  }
  return !EQ(angle, 0.0);
}
int main() {
  cin >> n;
  for (int i = 0; i < n; i++) {
    int x, y;
    cin >> x >> y;
    point[i] = Vector(x, y);
  }
  for (int i = 0; i < n; i++)
    for (int j = 0; j < i; j++) {
      inside[i][j] = inside[j][i] = true;
      if (!inside_polygon((point[i] + point[j]) * 0.5)) {
        inside[i][j] = inside[j][i] = false;
        continue;
      }
      for (int k = 0; k < n; k++) {
        int l = next(k);
        if (k != i && k != j && l != i && l != j &&
            segmentsegment(make_pair(point[i], point[j]),
                           make_pair(point[k], point[l]))) {
          inside[i][j] = inside[j][i] = false;
          break;
        }
      }
    }
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) dp[i][j] = -1;
  cout << solve(0, n - 1) << endl;
  return 0;
}
