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;
long long P(1000000007);
struct point {
  long long x, y;
  point() {}
  point(long long X, long long Y) : x(X), y(Y) {}
} a[300];
point operator-(point u, point v) { return point(u.x - v.x, u.y - v.y); }
long long dot(point u, point v) { return u.x * v.x + u.y * v.y; }
long long det(point u, point v) { return u.x * v.y - u.y * v.x; }
double dis(point u) { return sqrt(u.x * u.x + u.y * u.y); }
int sign(long long x) { return x > 0 ? 1 : x < 0 ? -1 : 0; }
int n;
bool see[300][300];
long long f[300][300];
void init() {
  scanf("%d", &n);
  for (int i = 1; i <= (n); ++i) {
    scanf("%I64d%I64d", &a[i].x, &a[i].y);
    a[i].x *= 2, a[i].y *= 2;
  }
  double ang(0);
  for (int i = 1; i <= (n); ++i)
    if (det(a[i % n + 1] - a[i], a[(i + 1) % n + 1] - a[i % n + 1]) >= 0)
      ang += acos(
          min(1., dot(a[i % n + 1] - a[i], a[(i + 1) % n + 1] - a[i % n + 1]) /
                      (dis(a[i % n + 1] - a[i]) *
                       dis(a[(i + 1) % n + 1] - a[i % n + 1]))));
    else
      ang -= acos(
          min(1., dot(a[i % n + 1] - a[i], a[(i + 1) % n + 1] - a[i % n + 1]) /
                      (dis(a[i % n + 1] - a[i]) *
                       dis(a[(i + 1) % n + 1] - a[i % n + 1]))));
  if (ang < 0) reverse(a + 1, a + n + 1);
  for (int u = 1; u <= (n); ++u)
    for (int v = (u + 1) % n + 1; v != u; v = v % n + 1) {
      see[u][v] = false;
      point t((a[u].x + a[v].x) / 2, (a[u].y + a[v].y) / 2);
      int cnt(0);
      for (int w = 1; w <= (n); ++w)
        if ((a[w].y - t.y) * (a[w % n + 1].y - t.y) <= 0) {
          point p = a[w], q = a[w % n + 1];
          if (p.y > q.y) swap(p, q);
          if (det(t - p, q - p) > 0 && q.y > t.y) ++cnt;
        }
      if (cnt & 1) see[u][v] = true;
      for (int w = 1; w <= (n); ++w)
        if (w != u && w % n + 1 != u && w != v && w % n + 1 != v) {
          if (sign(det(a[v] - a[u], a[w] - a[u])) *
                      sign(det(a[v] - a[u], a[w % n + 1] - a[u])) <
                  0 &&
              sign(det(a[w % n + 1] - a[w], a[u] - a[w])) *
                      sign(det(a[w % n + 1] - a[w], a[v] - a[w])) <
                  0)
            see[u][v] = false;
        }
      for (int w = 1; w <= (n); ++w)
        if (w != u && w != v && det(a[v] - a[u], a[w] - a[u]) == 0 &&
            dot(a[w] - a[u], a[v] - a[u]) > 0 &&
            dot(a[w] - a[v], a[u] - a[v]) > 0)
          see[u][v] = false;
      see[v][u] = see[u][v];
    }
  for (int i = 1; i <= (n); ++i) see[i][i % n + 1] = see[i % n + 1][i] = true;
}
void work() {
  for (int i = 1; i <= (n); ++i) f[i][i % n + 1] = 1;
  for (int d = (2); d <= (n - 1); ++d)
    for (int u = 1; u <= (n); ++u) {
      int v = (u + d - 1) % n + 1;
      for (int w = u % n + 1; w != v; w = w % n + 1)
        if (see[u][w] && see[v][w]) f[u][v] = (f[u][v] + f[u][w] * f[w][v]) % P;
    }
  printf("%I64d\n", f[1][n]);
}
int main() {
  init();
  work();
  return 0;
}
