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;
long long int modulo = 1e9 + 7;
int error[500][500];
long long int signo(long long int x) {
  if (x < 0) return -1;
  if (x > 0) return 1;
  return 0;
}
long long int prodvec(pair<long long int, long long int> p1,
                      pair<long long int, long long int> p2) {
  return p1.first * p2.second - p1.second * p2.first;
}
long long int prodesc(pair<long long int, long long int> p1,
                      pair<long long int, long long int> p2) {
  return p1.first * p2.first + p1.second * p2.second;
}
pair<long long int, long long int> operator-(
    pair<long long int, long long int> p1,
    pair<long long int, long long int> p2) {
  p1.first -= p2.first;
  p1.second -= p2.second;
  return p1;
}
pair<long long int, long long int> operator+(
    pair<long long int, long long int> p1,
    pair<long long int, long long int> p2) {
  p1.first += p2.first;
  p1.second += p2.second;
  return p1;
}
pair<long long int, long long int> operator*(
    long long int x, pair<long long int, long long int> p) {
  p.first *= x;
  p.second *= x;
  return p;
}
long long int memcalcula[500][500];
int calculado[500][500];
long long int calcula(int le, int ri) {
  if (le + 1 == ri or le + 2 == ri) return 1;
  long long int &mem = memcalcula[le][ri];
  if (calculado[le][ri]) return mem;
  calculado[le][ri] = 1;
  if (not error[le + 1][ri]) mem = calcula(le + 1, ri);
  for (int i = le + 2; i < ri; i++)
    if (not error[le][i] and not error[i][ri])
      mem = (mem + calcula(le, i) * calcula(i, ri)) % modulo;
  return mem;
}
bool enmedio(pair<long long int, long long int> p1,
             pair<long long int, long long int> p2,
             pair<long long int, long long int> medio) {
  pair<long long int, long long int> p1medio = medio - p1;
  pair<long long int, long long int> p1p2 = p2 - p1;
  if (prodvec(p1p2, p1medio) != 0) return false;
  long long int pe = prodesc(p1medio, p1p2);
  if (pe < 0) return false;
  long long int pp = prodesc(p1p2, p1p2);
  return pe <= pp;
}
int n;
pair<long long int, long long int> p[500];
void escribe(pair<long long int, long long int> p1) {
  cout << "(" << p1.first << "," << p1.second << ")";
}
bool vectorentre(pair<long long int, long long int> v1,
                 pair<long long int, long long int> v2,
                 pair<long long int, long long int> entre) {
  if (prodvec(v1, v2) >= 0)
    return prodvec(v1, entre) >= 0 and prodvec(entre, v2) >= 0;
  return prodvec(v1, entre) >= 0 or prodvec(entre, v2) >= 0;
}
int main() {
  cin >> n;
  for (int i = 0; i < n; i++) cin >> p[i].first >> p[i].second;
  long long int area = 0;
  for (int i = 1; i < n; i++) {
    int nexti = (i + 1) % n;
    area += prodvec(p[i] - p[0], p[nexti] - p[0]);
  }
  if (area < 0) reverse(p, p + n);
  for (int i = 0; i < n; i++) {
    int anti = (i - 1 + n) % n;
    int nexti = (i + 1) % n;
    pair<long long int, long long int> vant = p[anti] - p[i];
    pair<long long int, long long int> vnext = p[nexti] - p[i];
    for (int j = i + 2; j < n and not(i == 0 and j == n - 1); j++) {
      pair<long long int, long long int> v = p[j] - p[i];
      if (not vectorentre(vnext, vant, v)) error[i][j] = error[j][i] = 1;
      for (int k = 0; k < n and not error[i][j]; k++)
        if (k != j and k != i and enmedio(p[i], p[j], p[k]))
          error[i][j] = error[j][i] = 1;
      for (int k = 0; k < n and not error[i][j]; k++) {
        int nextk = (k + 1) % n;
        if (k != j and k != i and nextk != j and nextk != i) {
          pair<long long int, long long int> vk = p[nextk] - p[k];
          long long int spv1 = signo(prodvec(v, p[k] - p[i]));
          long long int spv2 = signo(prodvec(v, p[nextk] - p[i]));
          long long int spv3 = signo(prodvec(vk, p[i] - p[k]));
          long long int spv4 = signo(prodvec(vk, p[j] - p[k]));
          if (spv1 != 0 and spv2 != 0 and spv3 != 0 and spv4 != 0 and
              spv1 != spv2 and spv3 != spv4)
            error[i][j] = error[j][i] = 1;
        }
      }
    }
  }
  cout << calcula(0, n - 1) << endl;
}
