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;
static const int INF = 500000000;
template <class T>
void debug(T a, T b) {
  for (; a != b; ++a) cerr << *a << ' ';
  cerr << endl;
}
template <class T>
void chmin(T& a, const T& b) {
  if (a > b) a = b;
}
template <class T>
void chmax(T& a, const T& b) {
  if (a < b) a = b;
}
namespace std {
bool operator<(const complex<long long int>& a,
               const complex<long long int>& b) {
  return real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b);
}
}  // namespace std
inline long long int cross(const complex<long long int>& a,
                           const complex<long long int>& b) {
  return imag(conj(a) * b);
}
inline long long int dot(const complex<long long int>& a,
                         const complex<long long int>& b) {
  return real(conj(a) * b);
}
inline int sign(long long int a) {
  if (a == 0) return a;
  return a / abs(a);
}
struct L : public vector<complex<long long int> > {
  L(const complex<long long int>& a, const complex<long long int>& b) {
    push_back(a);
    push_back(b);
  }
};
struct C {
  complex<long long int> p;
  double r;
  C(const complex<long long int>& p, double r) : p(p), r(r) {}
};
inline int ccw(complex<long long int> a, complex<long long int> b,
               complex<long long int> c) {
  b -= a;
  c -= a;
  if (cross(b, c) > 0) return +1;
  if (cross(b, c) < 0) return -1;
  if (dot(b, c) < 0) return +2;
  if (norm(b) < norm(c)) return -2;
  return 0;
}
inline bool intersectLP(const complex<long long int>& l1,
                        const complex<long long int>& l2,
                        const complex<long long int>& p) {
  return abs(cross(l2 - p, l1 - p)) == 0;
}
inline bool intersectSS(const complex<long long int>& s1,
                        const complex<long long int>& s2,
                        const complex<long long int>& t1,
                        const complex<long long int>& t2) {
  return ccw(s1, s2, t1) * ccw(s1, s2, t2) <= 0 &&
         ccw(t1, t2, s1) * ccw(t1, t2, s2) <= 0;
}
vector<complex<long long int> > convex_hull(
    vector<complex<long long int> > ps) {
  int n = ps.size(), k = 0;
  sort(ps.begin(), ps.end());
  vector<complex<long long int> > ch(2 * n);
  for (int i = 0; i < n; ch[k++] = ps[i++])
    while (k >= 2 && ccw(ch[k - 2], ch[k - 1], ps[i]) <= 0) --k;
  for (int i = n - 2, t = k + 1; i >= 0; ch[k++] = ps[i--])
    while (k >= t && ccw(ch[k - 2], ch[k - 1], ps[i]) <= 0) --k;
  ch.resize(k - 1);
  return ch;
}
enum { OUT, ON, IN };
int contains(complex<long long int>* ps, int n,
             const complex<long long int>& p) {
  bool in = false;
  for (int i = 0; i < n; ++i) {
    complex<long long int> a = ps[i] - p, b = ps[(i + 1) % n] - p;
    if (imag(a) > imag(b)) swap(a, b);
    if (imag(a) <= 0 && 0 < imag(b))
      if (cross(a, b) < 0) in = !in;
    if (cross(a, b) == 0 && dot(a, b) <= 0) return ON;
  }
  return in ? IN : OUT;
}
int n;
complex<long long int> ps[205];
long long int dp[205][205];
long long int mod = 1000000007;
bool isok[205][205];
long long int rec(int l, int r) {
  if (r - l == 1) return 1;
  long long int& res = dp[l][r];
  if (res != -1) return res;
  res = 0;
  for (int i = l + 1; i < r; ++i)
    if (isok[l][i] && isok[i][r] && !intersectLP(ps[l], ps[r], ps[i])) {
      long long int A = rec(l, i), B = rec(i, r);
      res += A * B % mod;
    }
  res %= mod;
  return res;
}
int main() {
  cin >> n;
  for (int i = 0; i < (n); ++i) {
    long long int a, b;
    cin >> a >> b;
    a <<= 1;
    b <<= 1;
    ps[i].real(a);
    ps[i].imag(b);
  }
  ps[n] = ps[0];
  for (int i = 0; i < (n); ++i)
    for (int j = (i + 1); j < (n + 1); ++j) {
      if (i == 0 && j == n) continue;
      if (j - i == 1 || j - i == n - 1)
        isok[i][j] = 1;
      else {
        int cnt = 0;
        for (int k = 0; k < (n); ++k)
          if (intersectSS(ps[i], ps[j], ps[k], ps[k + 1])) ++cnt;
        if (cnt == 4) {
          complex<long long int> md =
              (ps[i] + ps[j]) / complex<long long int>(2, 0);
          if (contains(ps, n, md) == IN) isok[i][j] = 1;
        }
      }
    }
  memset(dp, -1, sizeof(dp));
  long long int res = rec(0, n - 1);
  cout << res << endl;
  return 0;
}
