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;
int n;
pair<double, double> a[205];
inline pair<double, double> operator-(pair<double, double> a,
                                      pair<double, double> s) {
  return pair<double, double>(a.first - s.first, a.second - s.second);
}
inline double operator*(pair<double, double> a, pair<double, double> s) {
  return a.first * s.second - a.second * s.first;
}
double S;
inline bool cat(pair<double, double> a, pair<double, double> b,
                pair<double, double> c, pair<double, double> d) {
  pair<double, double> w = c - a, u = b - a, v = d - c;
  double ms = u * v, ts1 = w * v, ts2 = w * u;
  if (ms != 0) {
    double p = ts1 / ms, q = ts2 / ms;
    if (p > 0 && p < 1 && q > 0 && q < 1) {
      return true;
    }
    if ((p > 0 && p < 1) && (q == 0 || q == 1)) {
      if (!(a == c || a == d || b == c || b == d)) return true;
    }
  } else {
    if ((a - b) * (c - a) == 0 && (a - b) * (d - a) == 0) {
      if (a > b) swap(a, b);
      if ((a < c && c < b) || (a < d && d < b)) return true;
    }
  }
  return false;
}
inline bool ngoai(int u, int v) {
  double ds = 0;
  for (int i = u; i <= v - 1; i++) ds += a[i] * a[i + 1];
  ds += a[v] * a[u];
  if (abs(ds) >= S) return true;
  ds = 0;
  for (int i = 1; i <= u - 1; i++) ds += a[i] * a[i + 1];
  ds += a[u] * a[v];
  for (int i = v; i <= n; i++) ds += a[i] * a[i + 1];
  if (abs(ds) > S) return true;
  return false;
}
long long f[205][205];
int main() {
  ios::sync_with_stdio(false);
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> a[i].first >> a[i].second;
  a[n + 1] = a[1];
  S = 0;
  for (int i = 1; i <= n; i++) S += a[i] * a[i + 1];
  S = abs(S);
  for (int i = 1; i <= n - 1; i++) f[i][i + 1] = 1;
  for (int j = 2; j <= n - 2; j++)
    for (int i = 1; i <= n; i++) {
      if (i + j > n) break;
      if (ngoai(i, i + j)) {
        f[i][i + j] = 0;
        continue;
      }
      int thu = 0;
      int u = i, v = i + j;
      for (int o = 1; o <= n; o++)
        if (cat(a[u], a[v], a[o], a[o + 1])) {
          thu = 1;
          break;
        }
      if (thu == 1) {
        f[u][v] = 0;
        continue;
      }
      for (int k = i + 1; k < v; k++)
        f[u][v] = (f[u][v] + (f[u][k] * f[k][v]) % 1000000007) % 1000000007;
    }
  long long ds = 0;
  for (int k = 2; k <= n - 1; k++)
    ds = (ds + (f[1][k] * f[k][n]) % 1000000007) % 1000000007;
  cout << ds;
}
