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;
ifstream in("input.txt");
long long n, sj = 0, k = 0;
bool d[500][500], pochasovoi = 0;
vector<pair<long long, long long> > pr;
struct point {
  long long x, y;
} a[500];
void read() {
  cin >> n;
  for (long long i = 0; i < n; i++) cin >> a[i].x >> a[i].y;
  for (long long i = 1; i < n; i++) {
    sj += a[i].x * a[i - 1].y - a[i].y * a[i - 1].x;
  }
  sj += a[0].x * a[n - 1].y - a[0].y * a[n - 1].x;
  if (sj > 0)
    pochasovoi = 1;
  else {
    for (int u = 0; u < n / 2; u++) {
      swap(a[u].x, a[n - 1 - u].x);
      swap(a[u].y, a[n - 1 - u].y);
    }
    pochasovoi = 1;
  }
}
long long pl(long long p1, long long p2, long long p3) {
  long long second = (a[p3].x - a[p1].x) * (a[p2].y - a[p1].y) -
                     (a[p3].y - a[p1].y) * (a[p2].x - a[p1].x);
  if (second == 0) return 0;
  if (second > 0) return 1;
  return -1;
}
bool cr(long long n1, long long n2) {
  for (long long c = 0; c < n; c++) {
    long long v = (c + 1) % n;
    if (c != n1 && c != n2 && v != n1 && v != n2)
      if (max(min(a[n1].x, a[n2].x), min(a[c].x, a[v].x)) <=
          min(max(a[n1].x, a[n2].x), max(a[c].x, a[v].x)))
        if (max(min(a[n1].y, a[n2].y), min(a[c].y, a[v].y)) <=
            min(max(a[n1].y, a[n2].y), max(a[c].y, a[v].y)))
          if (pl(n1, n2, c) * pl(n1, n2, v) <= 0)
            if (pl(c, v, n1) * pl(c, v, n2) <= 0) return 1;
  }
  return 0;
}
long long pl2(pair<double, double> p1, pair<double, double> p2, long long p3) {
  double second = (a[p3].x - p1.first) * (p2.second - p1.second) -
                  (a[p3].y - p1.second) * (p2.first - p1.first);
  if (second == 0) return 0;
  if (second > 0) return 1;
  return -1;
}
long long pl3(long long p1, long long p2, pair<double, double> p3) {
  double second = (p3.first - a[p1].x) * (a[p2].y - a[p1].y) -
                  (p3.second - a[p1].y) * (a[p2].x - a[p1].x);
  if (second == 0) return 0;
  if (second > 0) return 1;
  return -1;
}
bool outside(long long n1, long long n2) {
  point con = a[n2], pre = a[(n1 + n - 1) % n], nex = a[(n1 + 1) % n];
  nex.x -= a[n1].x, nex.y -= a[n1].y;
  con.x -= a[n1].x, con.y -= a[n1].y;
  pre.x -= a[n1].x, pre.y -= a[n1].y;
  double enp, enc, enn;
  enp = (double)asin(pre.y / sqrt((double)pre.y * pre.y + pre.x * pre.x));
  enc = (double)asin(con.y / sqrt((double)con.y * con.y + con.x * con.x));
  enn = (double)asin(nex.y / sqrt((double)nex.y * nex.y + nex.x * nex.x));
  if ((double)pre.x / sqrt((double)pre.y * pre.y + pre.x * pre.x) <= 0)
    enp = 3.14159265 - enp;
  if ((double)con.x / sqrt((double)con.y * con.y + con.x * con.x) <= 0)
    enc = 3.14159265 - enc;
  if ((double)nex.x / sqrt((double)nex.y * nex.y + nex.x * nex.x) <= 0)
    enn = 3.14159265 - enn;
  enc -= enn;
  enp -= enn;
  while (enc >= 2 * 3.14159265) enc -= 2 * 3.14159265;
  while (enp >= 2 * 3.14159265) enp -= 2 * 3.14159265;
  while (enc < 0) enc += 2 * 3.14159265;
  while (enp < 0) enp += 2 * 3.14159265;
  if (pochasovoi) {
    if (enc > enp) return 0;
    return 1;
  }
  if (enc > enp) return 1;
  return 0;
}
void diag() {
  for (long long i = 0; i < n; i++)
    for (long long j = i + 2; j < n; j++)
      if (!(i == 0 && j == n - 1)) {
        if (!cr(i, j))
          if (!outside(i, j)) {
            d[i][j] = 1;
            d[j][i] = 1;
            k++;
            pr.push_back(make_pair(i, j));
          }
      }
}
long long ans[500][500];
void din() {
  for (long long i = 0; i < n; i++) {
    ans[i][(i + 1) % n] = 1;
  }
  for (long long r = 2; r < n; r++)
    for (long long i = 0; i < n; i++)
      if (d[i][(i + r) % n] || r == n - 1) {
        long long dptr = (i + 1) % n;
        long long fk = (i + r) % n;
        while (dptr != fk) {
          ans[i][fk] =
              (ans[i][fk] + ((ans[i][dptr] * ans[dptr][fk]) % 1000000007)) %
              1000000007;
          dptr = (dptr + 1) % n;
        }
      }
  cout << ans[0][n - 1];
}
int main() {
  ios_base::sync_with_stdio(0);
  read();
  diag();
  din();
  return 0;
}
