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 mod = 1e9 + 7;
int n;
int dp[205][205];
using ll = long long;
struct pnt {
  int x, y;
  pnt(int x = 0, int y = 0) : x(x), y(y) {}
  pnt operator-(const pnt &a) { return pnt(x - a.x, y - a.y); }
  ll operator^(const pnt &a) { return 1ll * x * a.y - 1ll * y * a.x; }
  ll operator&(const pnt &a) { return 1ll * x * a.x + 1ll * y * a.y; }
  void input() { scanf("%d %d", &x, &y); }
} p[205];
bool ison(pnt a, pnt b, pnt c) {
  return (b - a & c - a) <= 0 && (b - a ^ c - a) == 0;
}
int has_intersection(pnt a, pnt b, pnt c, pnt d) {
  ll S = abs(a - b ^ c - d);
  if (S == 0) {
    if (abs(a - b ^ b - c) > 0) return 0;
    if (ison(a, c, d) || ison(b, c, d) || ison(c, a, b)) return 1;
    return 0;
  }
  if (abs(a - b ^ c - b) > S) return 0;
  if (abs(a - b ^ d - b) > S) return 0;
  if (abs(a - d ^ c - d) > S) return 0;
  if (abs(b - d ^ c - d) > S) return 0;
  return 1;
}
bool ok[205][205];
void add(int &x, int y) {
  x += y;
  if (x >= mod) x -= mod;
}
int mul(int x, int y) { return 1ll * x * y % mod; }
int is_diagonal_line(int f, int s, pnt *p, int n) {
  if ((f + 1) % n == s) return 2;
  if ((s + 1) % n == f) return 2;
  for (int i = 0; i < n; i++)
    if (i != f && i != s && ison(p[i], p[f], p[s])) return 0;
  for (int i = 0; i < n; i++) {
    int j = (i + 1) % n;
    if (i == f || i == s || j == f || j == s) continue;
    if (has_intersection(p[f], p[s], p[i], p[(i + 1) % n]) > 0) return 0;
  }
  for (int i = 0; i < 2; i++) {
    swap(f, s);
    ll S = 0;
    int cur = f;
    for (int cur = f, nxt; cur != s; cur = nxt) {
      nxt = (cur + 1) % n;
      S += p[cur] ^ p[nxt];
    }
    S += p[s] ^ p[f];
    if (S < 0) return 0;
  }
  return 1;
}
int main() {
  scanf("%d", &n);
  ll S = 0;
  for (int i = 0; i < n; i++) p[i].input();
  for (int i = 0; i < n; i++) S += p[i] ^ p[(i + 1) % n];
  if (S < 0) reverse(p, p + n);
  for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++) {
      ok[i][j] = is_diagonal_line(i, j, p, n);
      ok[j][i] = ok[i][j];
    }
  for (int i = 0; i < n; i++) {
    for (int j = i - 1; j >= 0; j--) {
      int &res = dp[i][j];
      res = 0;
      if (!ok[i][j]) continue;
      if (j == i - 1) {
        res = 1;
        continue;
      }
      for (int k = j + 1; k < i; k++)
        if (ok[i][k] && ok[j][k]) {
          add(res, mul(dp[k][j], dp[i][k]));
        }
    }
  }
  cout << dp[n - 1][0] << endl;
  return 0;
}
