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;
inline int getint() {
  int ans = 0, f = 1;
  char c = getchar();
  while (c > '9' || c < '0') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    ans = ans * 10 + c - '0';
    c = getchar();
  }
  return ans * f;
}
const long double eps = 1e-13, pi = 3.141592653589793238462643383;
inline bool equ(long double x, long double y) { return std::abs(x - y) < eps; }
struct point {
  long double x, y;
  point() {}
  point(long double X, long double Y) { x = X, y = Y; }
};
ostream& operator<<(ostream& os, const point p) {
  os << "(" << p.x << "," << p.y << ")";
  return os;
}
long double cross(point a, point b) { return (a.x * b.y - b.x * a.y); }
long double dot(point a, point b) { return (a.x * b.x + a.y * b.y); }
point operator-(point a, point b) { return point(a.x - b.x, a.y - b.y); }
point operator+(point a, point b) { return point(a.x + b.x, a.y + b.y); }
point operator*(point a, long double b) { return point(a.x * b, a.y * b); }
point operator/(point a, long double b) { return point(a.x / b, a.y / b); }
bool operator==(point a, point b) { return equ(a.x, b.x) && equ(a.y, b.y); }
bool operator!=(point a, point b) { return !(equ(a.x, b.x) && equ(a.y, b.y)); }
long double dis(point a, point b) {
  return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
point rotate(point v, long double ang) {
  return point(v.x * cos(ang) + v.y * sin(ang),
               v.y * cos(ang) - v.x * sin(ang));
}
struct line {
  point a, b;
  line() {}
  line(point A, point B) { a = A, b = B; }
};
line operator-(line l) { return line(l.b, l.a); }
point inter(line a, line b) {
  long double s1 = cross(b.a - a.a, b.b - a.a),
              s2 = cross(b.b - a.b, b.a - a.b);
  if (equ(s1 + s2, 0)) {
    return point(-1e12, -1e12);
  }
  return point(a.a.x + (a.b.x - a.a.x) / (s1 + s2) * s1,
               a.a.y + (a.b.y - a.a.y) / (s1 + s2) * s1);
}
bool isleft(line l, point p) { return cross(l.b - l.a, p - l.a) > -eps; }
bool isin(line a, line b) { return isleft(b, a.a); }
struct ray : line {
  ray() {}
  ray(point A, point B) { a = A, b = B; }
};
struct segment : ray {
  segment() {}
  segment(point A, point B) { a = A, b = B; }
  point mid() { return (a + b) / 2; }
  line pb() { return line(mid(), mid() + rotate(a - b, pi / 2)); }
};
bool ison(point p, line l) { return equ(cross(p - l.a, l.b - l.a), 0); }
bool ison(point p, ray r) {
  return ison(p, line(r)) && dot(p - r.a, r.b - r.a) > eps;
}
bool ison(point p, segment s) {
  return ison(p, ray(s)) && ison(p, ray(s.b, s.a));
}
bool iscross(line l, segment b) {
  if (ison(b.a, l) || ison(b.b, l)) return 1;
  if (equ(cross(l.b - l.a, b.b - b.a), 0)) return 0;
  point p = inter(l, line(b));
  return ison(p, b);
}
bool iscross(segment b, line l) { return iscross(l, b); }
bool iscross(segment a, segment b) {
  if (max(a.a.x, a.b.x) < min(b.a.x, b.b.x) - eps) return 0;
  if (max(a.a.y, a.b.y) < min(b.a.y, b.b.y) - eps) return 0;
  if (max(b.a.x, b.b.x) < min(a.a.x, a.b.x) - eps) return 0;
  if (max(b.a.x, b.b.x) < min(a.a.x, a.b.x) - eps) return 0;
  return iscross(line(a), b) && iscross(line(b), a);
}
struct circle {
  point o;
  long double r;
  circle() {}
  circle(point O, long double R) {
    o = O;
    r = R;
  }
  circle(long double x, long double y, long double R) {
    o = point(x, y);
    r = R;
  }
};
bool isin(point p, circle c) { return dis(p, c.o) - c.r < eps; }
bool ison(point p, circle c) { return equ(dis(p, c.o), c.r); }
struct triangle {
  point a, b, c;
  triangle() {}
  triangle(point A, point B, point C) {
    a = A;
    b = B;
    c = C;
  }
  bool iscollinear() { return equ(cross(b - a, c - a), 0); }
  point circumcenter() {
    if (!iscollinear()) return inter(segment(a, b).pb(), segment(a, c).pb());
    if (ison(b, segment(a, c))) return segment(a, c).mid();
    if (ison(a, segment(b, c))) return segment(b, c).mid();
    return segment(a, b).mid();
  }
  circle circumcircle() {
    point o = circumcenter();
    return circle(o, dis(o, a));
  }
};
const int N = 210, mod = 1e9 + 7;
point p[N];
int f[N][N];
int main() {
  int n = getint();
  for (int i = 0; i < n; i++) p[i].x = getint(), p[i].y = getint();
  long double s = 0;
  for (int i = 0; i < n; i++) s += cross(p[i], p[(i + 1) % n]);
  if (s > 0) reverse(p, p + n);
  for (int i = 0; i < n; i++) f[i][(i + 1) % n] = 1, f[i][i] = 1;
  for (int l = 3; l <= n; l++) {
    for (int i = 0, j = l - 1; j < n; i++, j++) {
      for (int k = i + 1; k < j; k++)
        if (cross(p[j] - p[i], p[k] - p[i]) > eps)
          f[i][j] = (f[i][j] + f[i][k] * 1ll * f[k][j]) % mod;
    }
  }
  cout << f[0][n - 1] << endl;
}
