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;
typedef long long arr32[310][310];
arr32 f, vis, s;
int n;
struct point {
  long long x, y;
  void init() {
    cin >> x >> y;
    x *= 2, y *= 2;
  }
} p[100010];
long long cx(int a, int b, int c) {
  return (p[b].x - p[a].x) * (p[c].y - p[a].y) -
         (p[b].y - p[a].y) * (p[c].x - p[a].x);
}
long long dj(int a, int b, int c) {
  return (p[b].x - p[a].x) * (p[c].x - p[a].x) +
         (p[b].y - p[a].y) * (p[c].y - p[a].y);
}
bool cross(int a, int b, int c, int d) {
  if (c == a || c == b) return false;
  if (d == a || d == b) return false;
  return ((cx(a, b, c) < 0) ^ (cx(a, b, d) < 0)) &&
         ((cx(c, d, a) < 0) ^ (cx(c, d, b) < 0));
}
bool Inline(int a, int b, int c) {
  return cx(a, b, c) == 0 && dj(c, a, b) <= 0;
}
bool check() {
  p[10000 + 1] = p[10000];
  p[10000 + 1].x += 1000000008;
  p[10000 + 1].y += 1000000009;
  int res = 0;
  for (int i = 1; i <= n; ++i)
    if (cross(10000, 10000 + 1, i, i + 1)) res ^= 1;
  return res;
}
bool in(int a, int b) {
  if (a == b - 1) return false;
  if (s[a][b] != -1) return s[a][b];
  for (int i = 1; i <= n; ++i)
    if (i != a && i != b && Inline(a, b, i)) return s[a][b] = 0;
  for (int i = 1; i <= n; ++i)
    if (cross(a, b, i, i % n + 1)) return s[a][b] = 0;
  p[10000].x = (p[a].x + p[b].x) / 2;
  p[10000].y = (p[a].y + p[b].y) / 2;
  return s[a][b] = check();
}
long long dp(int u, int v) {
  if (vis[u][v]) return f[u][v];
  vis[u][v] = 1;
  for (int i = u + 2; i <= v - 2; ++i)
    if (in(u, i) && in(i, v)) (f[u][v] += dp(u, i) * dp(i, v)) %= 1000000007;
  if (in(u, v - 1)) (f[u][v] += dp(u, v - 1)) %= 1000000007;
  if (in(u + 1, v)) (f[u][v] += dp(u + 1, v)) %= 1000000007;
  return f[u][v] = max(f[u][v], 1LL);
}
int main() {
  memset(s, -1, sizeof(s));
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    p[i].init();
  }
  p[0] = p[n], p[n + 1] = p[1];
  cout << dp(1, n) << endl;
}
