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>
const int mod = 1000000007;
int n, x[200], y[200], dp[200][200];
bool crs[200][200];
long long Cross(int x1, int y1, int x2, int y2) {
  return (long long)x1 * y2 - (long long)x2 * y1;
}
long long Dot(int x1, int y1, int x2, int y2) {
  return (long long)x1 * x2 + (long long)y1 * y2;
}
long long Dist(int x1, int y1, int x2, int y2) {
  return (long long)(x1 - x2) * (x1 - x2) + (long long)(y1 - y2) * (y1 - y2);
}
bool Intersect(int u1, int v1, int u2, int v2) {
  if (x[u1] == x[u2] && y[u1] == y[u2] || x[u1] == x[v2] && y[u1] == y[v2] ||
      x[v1] == x[u2] && y[v1] == y[u2] || x[v1] == x[v2] && y[v1] == y[v2])
    return false;
  long long t1 =
      Cross(x[v1] - x[u1], y[v1] - y[u1], x[u2] - x[u1], y[u2] - y[u1]);
  long long t2 =
      Cross(x[v1] - x[u1], y[v1] - y[u1], x[v2] - x[u1], y[v2] - y[u1]);
  long long t3 =
      Cross(x[v2] - x[u2], y[v2] - y[u2], x[u1] - x[u2], y[u1] - y[u2]);
  long long t4 =
      Cross(x[v2] - x[u2], y[v2] - y[u2], x[v1] - x[u2], y[v1] - y[u2]);
  if (!t1 && !t2 || !t3 && !t4) {
    long long p1 =
        Dot(x[v1] - x[u1], y[v1] - y[u1], x[u2] - x[u1], y[u2] - y[u1]);
    long long p2 =
        Dot(x[v1] - x[u1], y[v1] - y[u1], x[v2] - x[u1], y[v2] - y[u1]);
    long long p3 =
        Dot(x[v2] - x[u2], y[v2] - y[u2], x[u1] - x[u2], y[u1] - y[u2]);
    long long p4 =
        Dot(x[v2] - x[u2], y[v2] - y[u2], x[v1] - x[u2], y[v1] - y[u2]);
    if (p1 < 0 && p2 > 0 || p1 > 0 && p2 < 0 || p3 < 0 && p4 > 0 ||
        p3 > 0 && p4 < 0)
      return true;
    return false;
  }
  if ((t1 <= 0 && t2 >= 0 || t1 >= 0 && t2 <= 0) &&
      (t3 <= 0 && t4 >= 0 || t3 >= 0 && t4 <= 0))
    return true;
  return false;
}
int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; i++) scanf("%d%d", &x[i], &y[i]);
  for (int i = 0; i + 1 < n; i++) {
    for (int j = i + 1; j < n; j++) {
      if (i == 1 && j == 3) int stop = 0;
      crs[i][j] = true;
      long long a1 = Cross(x[j], y[j], x[i], y[i]),
                a2 = Cross(x[j], y[j], x[i], y[i]);
      for (int k = i; k != j; k++) a1 += Cross(x[k], y[k], x[k + 1], y[k + 1]);
      for (int k = i; k != j; k = (k + n - 1) % n)
        a2 += Cross(x[k], y[k], x[(k + n - 1) % n], y[(k + n - 1) % n]);
      if (a1 > 0 && a2 > 0 || a1 < 0 && a2 < 0) crs[i][j] = false;
      for (int k = 0; k < n && crs[i][j]; k++) {
        int p = (k + 1) % n;
        if (Intersect(k, p, i, j)) crs[i][j] = false;
        if (Cross(x[k] - x[i], y[k] - y[i], x[j] - x[i], y[j] - y[i]) == 0) {
          long long dot =
              Dot(x[k] - x[i], y[k] - y[i], x[j] - x[i], y[j] - y[i]);
          if (dot > 0 && dot < Dist(x[i], y[i], x[j], y[j])) crs[i][j] = false;
        }
      }
      crs[j][i] = crs[i][j];
    }
  }
  for (int i = 0; i + 1 < n; i++) dp[i][i + 1] = 1;
  for (int len = 2; len < n; len++) {
    for (int i = 0; i + len < n; i++) {
      int j = i + len;
      for (int k = i + 1; k < j; k++) {
        if (crs[i][k] && crs[j][k])
          dp[i][j] = ((long long)dp[i][k] * dp[k][j] + dp[i][j]) % mod;
      }
    }
  }
  printf("%d", dp[0][n - 1]);
  getchar();
  getchar();
  return 0;
}
