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, x[222], y[222], dp[222][222], can[222][222];
long long val(int x1, int y1, int x2, int y2, int x3, int y3) {
  long long vx = y2 - y1, vy = x1 - x2;
  return vx * (x1 - x3) + vy * (y1 - y3);
}
int sign(long long v) {
  if (v > 0) return 1;
  if (v == 0) return 0;
  return -1;
}
bool online(int x1, int y1, int x2, int y2, int x3, int y3) {
  long long v = val(x1, y1, x2, y2, x3, y3);
  return v == 0 && min(x1, x2) <= x3 && x3 <= max(x1, x2) &&
         min(y1, y2) <= y3 && y3 <= max(y1, y2);
}
bool cut(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) {
  long long v1 = val(x1, y1, x2, y2, x3, y3);
  long long v2 = val(x1, y1, x2, y2, x4, y4);
  long long v3 = val(x3, y3, x4, y4, x1, y1);
  long long v4 = val(x3, y3, x4, y4, x2, y2);
  if (online(x1, y1, x2, y2, x3, y3) || online(x1, y1, x2, y2, x4, y4) ||
      online(x3, y3, x4, y4, x1, y1) || online(x3, y3, x4, y4, x2, y2))
    return 1;
  return (sign(v1) * sign(v2) < 0 && sign(v3) * sign(v4) < 0);
}
bool iscan(int i, int j) {
  if ((i + 1) % n == j || (j + 1) % n == i) return 1;
  if (can[i][j] != -1) return can[i][j];
  for (int k = 0, _a = (n); k < _a; ++k)
    if (k != i && k != j && (k + 1) % n != i && (k + 1) % n != j)
      if (cut(x[i], y[i], x[j], y[j], x[k], y[k], x[(k + 1) % n],
              y[(k + 1) % n])) {
        can[i][j] = can[j][i] = 0;
        return 0;
      }
  for (int k = 0, _a = (n); k < _a; ++k)
    if (k != i && k != j && online(x[i], y[i], x[j], y[j], x[k], y[k])) {
      can[i][j] = can[j][i] = 0;
      return 0;
    }
  int xmid = (x[i] + x[j]), ymid = (y[i] + y[j]);
  int cnt = 0;
  for (int k = 0, _a = (n); k < _a; ++k) {
    int x1 = x[k] * 2, y1 = y[k] * 2;
    int x2 = x[(k + 1) % n] * 2, y2 = y[(k + 1) % n] * 2;
    if (y1 > y2) {
      swap(y1, y2);
      swap(x1, x2);
    }
    if (y1 == y2 || y2 < ymid || y1 >= ymid) continue;
    double vx = y2 - y1, vy = x1 - x2;
    double X = x1 + 1.0 * vy * (y1 - ymid) / vx;
    if (X < xmid) ++cnt;
  }
  can[i][j] = can[j][i] = cnt & 1;
  return can[i][j];
}
int f(int i, int j) {
  if ((j - i + n) % n <= 1) return 1;
  if (!iscan(i, j)) return 0;
  if (dp[i][j] != -1) return dp[i][j];
  int &res = dp[i][j];
  res = 0;
  for (int k = (i + 1) % n; k != j; k = (k + 1) % n)
    res = (res + 1ll * f(i, k) * f(k, j)) % 1000000007;
  return res;
}
int main() {
  cin >> n;
  for (int i = 0, _a = (n); i < _a; ++i) cin >> x[i] >> y[i];
  memset(can, -1, sizeof(can));
  memset(dp, -1, sizeof(dp));
  cout << f(0, n - 1) << endl;
  return 0;
}
