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;
template <class T>
void splitstr(const string &s, vector<T> &out) {
  istringstream in(s);
  out.clear();
  copy(istream_iterator<T>(in), istream_iterator<T>(), back_inserter(out));
}
template <class T>
T gcd(T a, T b) {
  return b ? gcd(b, a % b) : a;
}
static void redirect(int argc, const char **argv) {
  ios::sync_with_stdio(false);
  if (argc > 1) {
    static filebuf f;
    f.open(argv[1], ios::in);
    cin.rdbuf(&f);
    if (!cin) {
      cerr << "Failed to open '" << argv[1] << "'" << endl;
      exit(1);
    }
  }
  if (argc > 2) {
    static filebuf f;
    f.open(argv[2], ios::out | ios::trunc);
    cout.rdbuf(&f);
    if (!cout) {
      cerr << "Failed to open '" << argv[2] << "'" << endl;
    }
  }
}
static inline long long cross(const complex<long long> &a,
                              const complex<long long> &b) {
  return imag(conj(a) * b);
}
static inline long long cross(const complex<long long> &a,
                              const complex<long long> &b,
                              const complex<long long> &c) {
  return cross(b - a, c - a);
}
static long long polygon_area2(const std::vector<complex<long long> > &pnts) {
  long long ans = cross(pnts.back(), pnts[0]);
  for (size_t i = 1; i < pnts.size(); i++) ans += cross(pnts[i - 1], pnts[i]);
  return ans;
}
static int N;
static int nxt(int i) {
  i++;
  if (i == N)
    return 0;
  else
    return i;
}
int main(int argc, const char **argv) {
  bool valid[201][201] = {{}};
  redirect(argc, argv);
  cin >> N;
  vector<complex<long long> > pnts;
  for (int i = 0; i < N; i++) {
    int x, y;
    cin >> x >> y;
    pnts.push_back(complex<long long>(x, y));
  }
  if (polygon_area2(pnts) < 0) reverse(begin(pnts), end(pnts));
  long long dp[201][201] = {{}};
  for (int i = 0; i < N; i++) {
    dp[nxt(i)][i] = 1;
  }
  for (int g = 2; g < N; g++)
    for (int j = 0; j < N; j++) {
      long long ans = 0;
      int i = (j + g) % N;
      for (int k = nxt(j); k != i; k = nxt(k))
        if (cross(pnts[i], pnts[j], pnts[k]) > 0)
          ans = (ans + dp[k][j] * dp[i][k]) % 1000000007;
      dp[i][j] = ans;
    }
  cout << dp[0][1] << '\n';
  return 0;
}
