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;
struct point {
  long double x, y;
};
bool contained(point a, point b, point p) {
  return (
      (fabs((b.x - a.x) * (p.y - a.y) - (b.y - a.y) * (p.x - a.x)) < 10e-12) &&
      (min(a.x, b.x) <= p.x) && (max(a.x, b.x) >= p.x) &&
      (min(a.y, b.y) <= p.y) && (max(a.y, b.y) >= p.y));
}
bool intersect(point a, point b, point p, point q) {
  long double A1 = b.y - a.y;
  long double B1 = a.x - b.x;
  long double C1 = A1 * a.x + B1 * a.y;
  long double A2 = q.y - p.y;
  long double B2 = p.x - q.x;
  long double C2 = A2 * p.x + B2 * p.y;
  long double det = A1 * B2 - A2 * B1;
  if (det == 0) return 0;
  long double x = (B2 * C1 - B1 * C2) / det;
  long double y = (A1 * C2 - A2 * C1) / det;
  if ((min(a.x, b.x) <= x) && (x <= max(a.x, b.x)) && (min(a.y, b.y) <= y) &&
      (y <= max(a.y, b.y)))
    if ((min(p.x, q.x) <= x) && (x <= max(p.x, q.x)) && (min(p.y, q.y) <= y) &&
        (y <= max(p.y, q.y)))
      return 1;
  return 0;
}
long double angle(point a, point b, point c) {
  long double ans = atan2(a.y - b.y, a.x - b.x) - atan2(c.y - b.y, c.x - b.x);
  if (ans < 0) ans = -ans;
  if (ans > 3.14159265358979323) ans = 3.14159265358979323 - ans;
  return ans;
}
point poly[200];
bool bad[200][200];
long long dp[200][200];
int main() {
  int N;
  cin >> N;
  for (int i = 0; i < N; i++) cin >> poly[i].x >> poly[i].y;
  point mid;
  point rnd;
  rnd.x = 10000523;
  rnd.y = 10001357;
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      if (i == j) continue;
      bad[i][j] = 0;
      for (int k = 0; k < N; k++) {
        if ((k == i) || (k == j)) continue;
        bad[i][j] |= contained(poly[i], poly[j], poly[k]);
        if (((k + 1) % N == i) || ((k + 1) % N == j)) continue;
        bad[i][j] |= intersect(poly[i], poly[j], poly[k], poly[(k + 1) % N]);
      }
      mid.x = 0.5 * (poly[i].x + poly[j].x);
      mid.y = 0.5 * (poly[i].y + poly[j].y);
      int inter = 0;
      for (int k = 0; k < N; k++)
        inter += intersect(mid, rnd, poly[k], poly[(k + 1) % N]);
      if (!(inter % 2)) bad[i][j] = 1;
    }
  }
  for (int i = 0; i < N; i++) {
    bad[i][(i + 1) % N] = 0;
    bad[(i + 1) % N][i] = 0;
    dp[i][(i + 1) % N] = 1;
  }
  for (int i = 0; i < N; i++) {
    dp[i][(i + 2) % N] = 1 * (!bad[i][(i + 2) % N]);
  }
  int j, md;
  for (int dif = 3; dif <= (N - 1); dif++)
    for (int i = 0; i < N; i++) {
      j = (i + dif) % N;
      if (bad[i][j]) {
        dp[i][j] = 0;
        continue;
      }
      dp[i][j] = 0;
      for (int k = 1; k < dif; k++) {
        md = (i + k) % N;
        if ((!bad[i][md]) && (!bad[md][j])) {
          dp[i][j] += (dp[i][md] * dp[md][j]) % 1000000007;
        }
        dp[i][j] %= 1000000007;
      }
    }
  long long ans = 0;
  cout << dp[0][N - 1] << endl;
  return 0;
}
