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;
void _fill_int(int* p, int val, int rep) {
  int i;
  for (i = 0; i < rep; i++) p[i] = val;
}
int N;
signed long long X[300], Y[300];
signed long long mo = 1000000007;
int able[201][201];
signed long long dpdp[201][201];
vector<pair<signed long long, signed long long> > VV;
int sgn(signed long long a) {
  if (a > 0) return 1;
  if (a < 0) return -1;
  return 0;
}
int inside(double x, double y,
           vector<pair<signed long long, signed long long> >& V) {
  int num = 0, n = V.size(), i;
  for (i = 0; i < n; i++)
    if (x == V[i].first && y == V[i].second) return 2;
  for (i = 0; i < n; i++) {
    double dx = V[(i + 1) % n].first - V[i].first,
           dy = V[(i + 1) % n].second - V[i].second;
    double dx2 = x - V[i].first, dy2 = y - V[i].second;
    if (fabs(dx * dy2 - dx2 * dy) >= 1e-9) continue;
    if (dx != 0) {
      if (dx2 / dx >= 0 && dx2 / dx <= 1) return 1;
    } else if (dy2 / dy >= 0 && dy2 / dy <= 1)
      return 1;
  }
  for (i = 0; i < n; i++) {
    signed long long x1 = V[i].first, y1 = V[i].second;
    signed long long x2 = V[(i + 1) % n].first, y2 = V[(i + 1) % n].second;
    if (y1 == y2) continue;
    if (y1 == y) {
      if (x1 >= x && y2 < y) num++;
    } else if (y2 == y) {
      if (x2 >= x && y1 < y) num--;
    } else if (y1 > y && y2 < y) {
      double xx = x1 + (x2 - x1) * (double)(y - y1) / (y2 - y1);
      if (xx >= x) num++;
    } else if (y1 < y && y2 > y) {
      double xx = x1 + (x2 - x1) * (double)(y - y1) / (y2 - y1);
      if (xx >= x) num--;
    }
  }
  return num != 0;
}
int test(int aa, int bb) {
  if ((aa + 1) % N == bb || (bb + 1) % N == aa) return 1;
  int i;
  for (i = 0; i < N; i++)
    if (i != aa && i != bb) {
      signed long long x1 = X[i] - X[aa];
      signed long long y1 = Y[i] - Y[aa];
      signed long long x2 = X[bb] - X[aa];
      signed long long y2 = Y[bb] - Y[aa];
      if (x1 * y2 - x2 * y1 != 0) continue;
      if (x2 != 0) {
        double d = x1 / (double)x2;
        if (d >= 0 && d <= 1) return 0;
      }
      if (y2 != 0) {
        double d = y1 / (double)y2;
        if (d >= 0 && d <= 1) return 0;
      }
    }
  for (i = 0; i < N; i++) {
    if (aa == i || bb == i) continue;
    if (aa == (i + 1) % N || bb == (i + 1) % N) continue;
    signed long long x1 = X[(i + 1) % N] - X[i];
    signed long long y1 = Y[(i + 1) % N] - Y[i];
    signed long long x2 = X[aa] - X[i];
    signed long long y2 = Y[aa] - Y[i];
    signed long long x3 = X[bb] - X[i];
    signed long long y3 = Y[bb] - Y[i];
    if (sgn(x2 * y1 - x1 * y2) * sgn(x3 * y1 - x1 * y3) >= 0) continue;
    x1 = X[i] - X[aa];
    y1 = Y[i] - Y[aa];
    x2 = X[(i + 1) % N] - X[aa];
    y2 = Y[(i + 1) % N] - Y[aa];
    x3 = X[bb] - X[aa];
    y3 = Y[bb] - Y[aa];
    if (sgn(x2 * y3 - x3 * y2) * sgn(x1 * y3 - x3 * y1) >= 0) continue;
    return 0;
  }
  double xx1 = X[bb] - X[aa];
  double yy1 = Y[bb] - Y[aa];
  double rr = sqrt(xx1 * xx1 + yy1 * yy1);
  xx1 = X[aa] + xx1 / 10 / rr;
  yy1 = Y[aa] + yy1 / 10 / rr;
  return inside(xx1, yy1, VV) > 0;
}
signed long long dodo(int s, int e) {
  if (dpdp[s][e] >= 0) return dpdp[s][e];
  if (able[s][e] == 0) return dpdp[s][e] = 0;
  if (s + 2 >= e) return dpdp[s][e] = 1;
  dpdp[s][e] = 0;
  for (int x = s + 1; x < e; x++)
    if (able[s][x] && able[x][e] && able[e][s])
      dpdp[s][e] = (dpdp[s][e] + dodo(s, x) * dodo(x, e)) % mo;
  return dpdp[s][e];
}
void solve() {
  int f, i, j, k, l, x, y;
  cin >> N;
  for (i = 0; i < N; i++) cin >> X[i] >> Y[i];
  for (i = 0; i < N; i++) VV.push_back(make_pair(X[i], Y[i]));
  for (x = 0; x < N; x++)
    for (y = x + 1; y < N; y++) able[x][y] = able[y][x] = test(x, y);
  _fill_int((int*)dpdp, -1, sizeof(dpdp) / 4);
  cout << dodo(0, N - 1) << endl;
}
int main(int argc, char** argv) {
  string s;
  if (argc == 1) ios::sync_with_stdio(false);
  for (int i = 1; i < argc; i++) s += argv[i], s += '\n';
  for (int i = s.size() - 1; i >= 0; i--) ungetc(s[i], stdin);
  solve();
  return 0;
}
