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 debug;
const int MAX = 205, MOD = 1000000007;
int dp[MAX][MAX], moze[MAX][MAX], x[MAX], y[MAX], n;
int Brtoc(int t1, int t2) {
  if (t2 > t1) return t2 - t1 + 1;
  return n - t1 + t2 + 1;
}
int Slj(int t) { return (t + 1) % n; }
int Prije(int t) { return (t + n - 1) % n; }
long long Ccw(int a, int b, int c) {
  long long r = (long long)x[a] * (y[b] - y[c]) +
                (long long)x[b] * (y[c] - y[a]) +
                (long long)x[c] * (y[a] - y[b]);
  ;
  if (r < 0) return -1;
  if (r > 0) return 1;
  return 0;
}
long long Povrsina(int t1, int t2) {
  int i;
  long long r = 0;
  for (i = t1; i != t2; i = Slj(i))
    r += (long long)x[i] * y[Slj(i)] - (long long)y[i] * x[Slj(i)];
  r += (long long)x[t2] * y[t1] - (long long)y[t2] * x[t1];
  return r;
}
int Sijece(int a1, int a2, int b1, int b2, int st) {
  if (!Ccw(a1, a2, b1) && !Ccw(a1, a2, b2) && !Ccw(b1, b2, a1) &&
      !Ccw(b1, b2, a2)) {
    if (st) {
      return (x[b1] > min(x[a1], x[a2]) && x[b1] < max(x[a1], x[a2]) &&
              y[b1] >= min(y[a1], y[a2]) && y[b1] <= max(y[a1], y[a2])) ||
             (x[b1] >= min(x[a1], x[a2]) && x[b1] <= max(x[a1], x[a2]) &&
              y[b1] > min(y[a1], y[a2]) && y[b1] < max(y[a1], y[a2])) ||
             (x[b2] > min(x[a1], x[a2]) && x[b2] < max(x[a1], x[a2]) &&
              y[b2] >= min(y[a1], y[a2]) && y[b2] <= max(y[a1], y[a2])) ||
             (x[b2] >= min(x[a1], x[a2]) && x[b2] <= max(x[a1], x[a2]) &&
              y[b2] > min(y[a1], y[a2]) && y[b2] < max(y[a1], y[a2]));
    }
    return ((x[b1] >= min(x[a1], x[a2]) && x[b1] <= max(x[a1], x[a2]) &&
             y[b1] >= min(y[a1], y[a2]) && y[b1] <= max(y[a1], y[a2])) ||
            x[b2] >= min(x[a1], x[a2]) && x[b2] <= max(x[a1], x[a2]) &&
                y[b2] >= min(y[a1], y[a2]) && y[b2] <= max(y[a1], y[a2]));
  }
  return !st && Ccw(a1, a2, b1) * Ccw(a1, a2, b2) <= 0 &&
         Ccw(b1, b2, a1) * Ccw(b1, b2, a2) <= 0;
}
int Rek(int t1, int t2) {
  int i;
  if (dp[t1][t2] != -1) return dp[t1][t2];
  if (Brtoc(t1, t2) == 3) {
    return dp[t1][t2] = moze[t1][t2] * moze[t1][Slj(t1)] * moze[Slj(t1)][t2];
  }
  if (Brtoc(t1, t2) == 2) {
    return dp[t1][t2] = moze[t1][t2];
  }
  if (Brtoc(t1, t2) == 1) return dp[t1][t2] = 1;
  dp[t1][t2] = 0;
  for (i = Slj(t1); i != t2; i = Slj(i))
    if (moze[t1][i] && moze[t2][i])
      dp[t1][t2] = (dp[t1][t2] + (long long)Rek(t1, i) * Rek(i, t2)) % MOD;
  return dp[t1][t2];
}
int main() {
  int i, j, k, st;
  long long pov = 0;
  scanf("%d", &n);
  for (i = 0; i < n; i++) scanf("%d%d", &x[i], &y[i]);
  pov = Povrsina(0, n - 1);
  memset(dp, -1, sizeof dp);
  for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
      moze[i][j] = 1;
      if (j == Slj(i) || j == Prije(i)) continue;
      if (i == j) moze[i][j] = 0;
      for (k = 0; k < n; k++) {
        st = 0;
        if (k == i || k == j || Slj(k) == i || Slj(k) == j) st = 1;
        if (i == 0 && j == 2 && k == 1) {
          debug = 1;
          debug = 0;
        }
        if (Sijece(i, j, k, Slj(k), st)) {
          moze[i][j] = 0;
        }
      }
      if (abs(Povrsina(i, j)) > abs(pov) || abs(Povrsina(j, i)) > abs(pov)) {
        moze[i][j] = 0;
      }
    }
  }
  printf("%d\n", Rek(0, n - 1));
  return 0;
}
