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 N = 222, MOD = 1e9 + 7;
const double eps = 1e-8;
struct P {
  double x, y;
  P() {}
  P(double x, double y) {
    this->x = x;
    this->y = y;
  }
  P operator+(const P &c) const { return P(x + c.x, y + c.y); }
  P operator-(const P &c) const { return P(x - c.x, y - c.y); }
  P operator*(const double &c) const { return P(x * c, y * c); }
  P operator/(const double &c) const { return P(x / c, y / c); }
};
int n;
P p[N];
bool f[N][N];
long long dp[N][N];
P read() {
  double x, y;
  scanf("%lf%lf", &x, &y);
  return P(x, y);
}
void print(P p) { printf("%lf %lf\n", p.x, p.y); }
int sign(double x) { return (x > eps) - (x < -eps); }
double dot(P a, P b) { return a.x * b.x + a.y * b.y; }
double cross(P a, P b) { return a.x * b.y - b.x * a.y; }
bool isSS0(P a1, P a2, P b1, P b2) {
  double c1 = cross(a2 - a1, b1 - a1), c2 = cross(a2 - a1, b2 - a1),
         c3 = cross(b2 - b1, a1 - b1), c4 = cross(b2 - b1, a2 - b1);
  return sign(c1) * sign(c2) < 0 && sign(c3) * sign(c4) < 0;
}
bool isSS1(P a1, P a2, P b1, P b2) {
  double c1 = cross(a2 - a1, b1 - a1), c2 = cross(a2 - a1, b2 - a1),
         c3 = cross(b2 - b1, a1 - b1), c4 = cross(b2 - b1, a2 - b1);
  return sign(max(a1.x, a2.x) - min(b1.x, b2.x)) >= 0 &&
         sign(max(b1.x, b2.x) - min(a1.x, a2.x)) >= 0 &&
         sign(max(a1.y, a2.y) - min(b1.y, b2.y)) >= 0 &&
         sign(max(b1.y, b2.y) - min(a1.y, a2.y)) >= 0 &&
         sign(c1) * sign(c2) <= 0 && sign(c3) * sign(c4) <= 0;
}
bool onS0(P p, P a, P b) {
  return sign(cross(p - a, b - a)) == 0 && sign(dot(p - a, p - b)) < 0;
}
bool onS1(P p, P a, P b) {
  return sign(cross(p - a, b - a)) == 0 && sign(dot(p - a, p - b)) <= 0;
}
int Pinploy(P o, P *p, int n) {
  int res = 0;
  for (int i = (0); i < (n); i++) {
    P u = p[i], v = p[(i + 1) % n];
    if (onS1(o, u, v)) return -1;
    int k = sign(cross(v - u, o - u));
    int d1 = sign(u.y - o.y);
    int d2 = sign(v.y - o.y);
    if (k > 0 && d1 <= 0 && d2 > 0) ++res;
    if (k < 0 && d2 <= 0 && d1 > 0) --res;
  }
  return res != 0;
}
bool check(int x, int y) {
  for (int i = (0); i < (n); i++) {
    int j = (i + 1) % n;
    if (i == x || i == y || j == x || j == y) {
      if (isSS0(p[x], p[y], p[i], p[j])) return 0;
    } else {
      if (isSS1(p[x], p[y], p[i], p[j])) return 0;
    }
  }
  if (Pinploy((p[x] + p[y]) / 2, p, n) == 0) return 0;
  return 1;
}
void upd(long long &a, long long b) {
  a += b;
  if (a >= MOD) a -= MOD;
}
int main() {
  scanf("%d", &n);
  for (int i = (0); i < (n); i++) p[i] = read();
  for (int i = (0); i < (n); i++)
    for (int j = (i + 1); j < (n); j++) f[i][j] = f[j][i] = check(i, j);
  for (int i = (0); i < (n - 1); i++) dp[i][i + 1] = 1;
  for (int len = (3); len < (n + 1); len++) {
    for (int i = 0, j = i + len - 1; j < n; ++i, ++j)
      if (f[i][j]) {
        dp[i][j] = 0;
        for (int k = (i + 1); k < (j); k++) {
          if (f[i][k] && f[k][j] && sign(cross(p[i] - p[j], p[i] - p[k])))
            upd(dp[i][j], dp[i][k] * dp[k][j] % MOD);
        }
      }
  }
  printf("%lld\n", dp[0][n - 1]);
  return 0;
}
