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 inv = 1000000000;
const int minv = -inv;
const int max_n = 210;
const long long modref = 1000000007ll;
struct point {
  long long xc, yc;
  point() {}
  point(long long xc_, long long yc_) {
    xc = xc_;
    yc = yc_;
  }
};
point operator+(const point &a, const point &b) {
  return point(a.xc + b.xc, a.yc + b.yc);
}
point operator-(const point &a, const point &b) {
  return point(a.xc - b.xc, a.yc - b.yc);
}
long long operator*(const point &a, const point &b) {
  return (a.xc * b.xc + a.yc * b.yc);
}
long long operator^(const point &a, const point &b) {
  return (a.xc * b.yc - a.yc * b.xc);
}
bool leftturn(point X1, point X2, point X3) {
  return (((X2 - X1) ^ (X3 - X2)) > 0ll);
}
bool straight(point X1, point X2, point X3) {
  return (((X2 - X1) ^ (X3 - X2)) == 0ll);
}
bool segmentsintersect(point A1, point A2, point B1, point B2) {
  if (straight(A1, A2, B1) or straight(A1, A2, B2) or straight(A1, B1, B2) or
      straight(A2, B1, B2))
    return false;
  bool check1 = (leftturn(A1, A2, B1) xor leftturn(A1, A2, B2));
  bool check2 = (leftturn(B1, B2, A1) xor leftturn(B1, B2, A2));
  return (check1 and check2);
}
int n;
point P[max_n];
long long dp[max_n][max_n];
bool valid[max_n][max_n];
vector<int> V;
long long area(vector<int> &V) {
  long long ret = 0ll;
  int Vsz = (int)V.size();
  for (int i = 0; i < Vsz; ++i) ret += (P[V[i]] ^ P[V[(i + 1) % Vsz]]);
  return ret;
}
int main() {
  scanf("%d", &n);
  V.resize(0);
  for (int i = 0; i < n; ++i) {
    cin >> P[i].xc;
    cin >> P[i].yc;
    V.push_back(i);
  }
  if (area(V) < 0ll) reverse(P, P + n);
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j)
      if (i != j) {
        valid[i][j] = true;
        for (int k = 0; k < n; ++k)
          if (segmentsintersect(P[i], P[j], P[k], P[(k + 1) % n])) {
            valid[i][j] = false;
            break;
          }
        for (int k = 0; k < n; ++k)
          if (k != i and k != j and straight(P[i], P[j], P[k]) and
              min(pair<int, int>(P[i].xc, P[i].yc),
                  pair<int, int>(P[j].xc, P[j].yc)) <=
                  pair<int, int>(P[k].xc, P[k].yc) and
              pair<int, int>(P[k].xc, P[k].yc) <=
                  max(pair<int, int>(P[i].xc, P[i].yc),
                      pair<int, int>(P[j].xc, P[j].yc))) {
            valid[i][j] = false;
            break;
          }
        int l = i, r = j;
        V.resize(0);
        for (int k = l; k != r; k = (k + 1) % n) V.push_back(k);
        V.push_back(r);
        if (area(V) < 0ll) valid[i][j] = false;
        V.resize(0);
        for (int k = r; k != l; k = (k + 1) % n) V.push_back(k);
        V.push_back(l);
        if (area(V) < 0ll) valid[i][j] = false;
      }
  for (int i = 0; i < n; ++i) {
    dp[i][(i + 1) % n] = 1ll;
    dp[i][(i + 2) % n] = 1ll;
  }
  for (int len = 3; len < n; ++len)
    for (int i = 0; i < n; ++i) {
      int l = i, r = (i + len) % n;
      V.resize(0);
      for (int j = l; j != r; j = (j + 1) % n) V.push_back(j);
      V.push_back(r);
      dp[l][r] = 0ll;
      for (int m = 1; m < (int)V.size() - 1; ++m)
        if (valid[l][V[m]] and valid[r][V[m]]) {
          dp[l][r] += (dp[l][V[m]] * dp[V[m]][r]);
          dp[l][r] %= modref;
        }
    }
  cout << dp[0][n - 1] << "\n";
  return 0;
}
