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 mm = 1000000007;
struct pt {
  long long x, y;
} a[501];
struct pt2 {
  double x, y;
} w;
long long f[501][501];
int i, j, k, n, m;
long long cp(pt o, pt a, pt b) {
  return (a.x - o.x) * (b.y - o.y) - (b.x - o.x) * (a.y - o.y);
}
double cp2(pt2 o, pt2 a, pt2 b) {
  return (a.x - o.x) * (b.y - o.y) - (b.x - o.x) * (a.y - o.y);
}
bool cinter(pt a, pt b, pt c, pt d) {
  long long t1, t2, r1, r2;
  t1 = cp(a, b, c);
  t2 = cp(a, b, d);
  if (t1 > 0 && t2 > 0 || t1 < 0 && t2 < 0)
    r1 = 1;
  else if (t1 == 0 || t2 == 0)
    r1 = 0;
  else
    r1 = -1;
  t1 = cp(c, d, a);
  t2 = cp(c, d, b);
  if (t1 > 0 && t2 > 0 || t1 < 0 && t2 < 0)
    r2 = 1;
  else if (t1 == 0 || t2 == 0)
    r2 = 0;
  else
    r2 = -1;
  if (r1 > 0 || r2 > 0) return 0;
  if (r1 == 0 && r2 == 0) {
    if (a.x > b.x) swap(a, b);
    if (c.x > d.x) swap(c, d);
    if (a.x > c.x) swap(a, c), swap(b, d);
    if (c.x > b.x) return 0;
    if (a.y > c.y) swap(a, c), swap(b, d);
    if (c.y > b.y) return 0;
    return 1;
  }
  return 1;
}
bool check(int t1, int t2) {
  int i;
  for (i = 1; i <= n; i++)
    if (t1 != i && t2 != i && t1 != ((i + 1) > n ? 1 : i + 1) &&
        t2 != ((i + 1) > n ? 1 : i + 1) && cinter(a[t1], a[t2], a[i], a[i + 1]))
      return 0;
  for (i = 1; i <= n; i++)
    if (t1 != i && t2 != i && cp(a[t1], a[i], a[t2]) == 0 &&
        min(a[t1].x, a[t2].x) <= a[i].x && a[i].x <= max(a[t1].x, a[t2].x) &&
        min(a[t1].y, a[t2].y) <= a[i].y && a[i].y <= max(a[t1].y, a[t2].y))
      return 0;
  return 1;
}
bool cinside(int t1, int t2) {
  int i, k;
  pt2 p, a1, a2;
  p.x = (double)(a[t1].x + a[t2].x) / 2;
  p.y = (double)(a[t1].y + a[t2].y) / 2;
  for (i = 1, k = 0; i <= n; i++) {
    a1.x = a[i].x;
    a1.y = a[i].y;
    a2.x = a[i + 1].x;
    a2.y = a[i + 1].y;
    if (cp2(a1, a2, w) * cp2(a1, a2, p) < 0 &&
        cp2(w, p, a1) * cp2(w, p, a2) < 0)
      k++;
  }
  return k & 1;
}
long long work(int l, int r) {
  int i;
  if (f[l][r] != -1) return f[l][r];
  if ((!check(l, r) || !cinside(l, r)) && l < r - 1 && (l != 1 || r != n))
    return f[l][r] = 0;
  if (l >= r - 2) return f[l][r] = 1;
  f[l][r] = 0;
  for (i = l + 1; i < r; i++)
    f[l][r] = (f[l][r] + work(l, i) * work(i, r)) % mm;
  return f[l][r];
}
int main() {
  scanf("%d", &n);
  memset(f, -1, sizeof(f));
  w.x = 975143117;
  w.y = 76315731;
  for (i = 1; i <= n; i++) scanf("%d%d", &j, &k), a[i].x = j, a[i].y = k;
  a[n + 1] = a[1];
  work(1, n);
  cout << f[1][n] << endl;
  return 0;
}
