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;
const int SIZE = 250;
const int MOD = 1e9 + 7;
int n;
struct Point {
  long long x, y;
  Point(long long _x = 0, long long _y = 0) : x(_x), y(_y) {}
  Point operator-(const Point& b) const { return Point(x - b.x, y - b.y); }
  long long operator^(const Point& b) const { return x * b.x + y * b.y; }
  long long operator*(const Point& b) const { return x * b.y - y * b.x; }
  void read() { scanf("%I64d%I64d", &x, &y); }
} p[SIZE + SIZE];
int ng(long long x) {
  if (x > 0) return 1;
  if (x < 0) return -1;
  return 0;
}
bool XX(Point& A, Point& B, Point& C, Point& D) {
  return ng((C - A) * (B - A)) * ng((B - A) * (D - A)) > 0 &&
         ng((A - D) * (C - D)) * ng((C - D) * (B - D)) > 0;
}
long long AREA;
void init() {
  for (int i = 0; i < (n); ++i) AREA += p[i + 1] * p[i];
  if (AREA < 0) AREA = -AREA;
}
bool valid[SIZE][SIZE];
bool valid_edge(int x, int y) {
  long long r1 = p[x] * p[y], r2 = p[y] * p[x];
  for (int i = (x); i < (y); ++i) {
    r1 += p[i + 1] * p[i];
  }
  for (int i = (y); i < (x + n); ++i) {
    r2 += p[i + 1] * p[i];
  }
  if (abs(r1) >= AREA || abs(r2) >= AREA) return false;
  for (int i = 0; i < (n); ++i) {
    if (i == x || i == y) continue;
    if (!((p[i] - p[x]) * (p[y] - p[x]))) {
      if (((p[i] - p[x]) ^ (p[i] - p[y])) <= 0) return false;
    }
  }
  for (int i = 0; i < (n); ++i) {
    if (XX(p[x], p[y], p[i], p[i + 1])) return false;
  }
  return true;
}
long long dp[SIZE][SIZE];
int main() {
  scanf("%d", &(n));
  for (int i = 0; i < (n); ++i) {
    p[i].read();
    p[i + n] = p[i];
  }
  init();
  for (int i = 0; i < (n - 1); ++i) valid[i][i + 1] = valid[i + 1][i] = true;
  valid[0][n - 1] = valid[n - 1][0] = true;
  for (int i = 0; i < (n); ++i)
    for (int j = (i + 2); j < (n); ++j) {
      if (abs(i - j) != n - 1) valid[i][j] = valid[j][i] = valid_edge(i, j);
    }
  for (int i = 0; i < (n); ++i) dp[i][1] = 1;
  for (int dd = (2); dd < (n); ++dd) {
    for (int i = 0; i < (n); ++i) {
      int ll = i, rr = (i + dd) % n;
      if (!valid[ll][rr]) continue;
      for (int k = 1; k < dd; k++) {
        if (!valid[ll][(ll + k) % n] || !valid[rr][(ll + k) % n]) {
          continue;
        }
        dp[i][dd] = (dp[i][dd] + dp[i][k] * dp[(i + k) % n][dd - k]) % MOD;
      }
    }
  }
  cout << dp[0][n - 1] << endl;
  return 0;
}
