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 MaxN = 210;
const int Mod = 1000000007;
const double eps = 1e-9;
const double inf = 12345678.64;
inline bool lt(double a, double b) { return a + eps < b; }
inline bool gt(double a, double b) { return lt(b, a); }
inline bool eq(double a, double b) { return !lt(a, b) && !lt(b, a); }
inline bool lteq(double a, double b) { return lt(a, b) || eq(a, b); }
inline bool gteq(double a, double b) { return gt(a, b) || eq(a, b); }
inline int sgn(double first) {
  if (lt(first, 0)) return -1;
  if (gt(first, 0)) return 1;
  return 0;
}
inline int ccw(pair<double, double> A, pair<double, double> B,
               pair<double, double> C) {
  return sgn(A.first * (B.second - C.second) + B.first * (C.second - A.second) +
             C.first * (A.second - B.second));
}
inline bool EQ(pair<double, double> A, pair<double, double> B) {
  return eq(A.first, B.first) && eq(A.second, B.second);
}
bool intersect(pair<double, double> A, pair<double, double> B,
               pair<double, double> C, pair<double, double> D) {
  if (EQ(A, C) || EQ(A, D) || EQ(B, C) || EQ(B, D)) return false;
  int c1 = ccw(A, B, C), c2 = ccw(A, B, D);
  int c3 = ccw(C, D, A), c4 = ccw(C, D, B);
  if (c1 == 0 && c2 == 0) {
    if (gt(min(C.first, D.first), max(A.first, B.first))) return false;
    if (gt(min(A.first, B.first), max(C.first, D.first))) return false;
    if (gt(min(C.second, D.second), max(A.second, B.second))) return false;
    if (gt(min(A.second, B.second), max(C.second, D.second))) return false;
    return true;
  }
  if (c1 == c2 || c3 == c4) return false;
  return true;
}
int N, dp[MaxN][MaxN];
pair<double, double> P[MaxN];
bool ok[MaxN][MaxN];
int f(int i, int j) {
  if (j - i <= 2) return 1;
  if (dp[i][j] != -1) return dp[i][j];
  int ret = 0;
  for (int k = i + 1; k < j; ++k)
    if (ok[i][k] && ok[k][j] && ccw(P[i], P[k], P[j]) != 0)
      ret = (ret + (long long)f(i, k) * f(k, j) % Mod) % Mod;
  return dp[i][j] = ret;
}
inline bool on(double px, double py, pair<double, double> A,
               pair<double, double> B) {
  double c = px * (A.second - B.second) + A.first * (B.second - py) +
             B.first * (py - A.second);
  if (eq(c, 0) && gteq(px, min(A.first, B.first)) &&
      lteq(px, max(A.first, B.first)) && gteq(py, min(A.second, B.second)) &&
      lteq(py, max(A.second, B.second)))
    return true;
  return false;
}
inline bool boundary(double px, double py) {
  for (int i = 0; i < N; ++i)
    if (on(px, py, P[i], P[i + 1])) return true;
  return false;
}
inline bool inside(double px, double py) {
  int ret = 0;
  for (int i = 0; i < N; ++i)
    if (intersect(P[i], P[i + 1], pair<double, double>(px, py),
                  pair<double, double>(-inf + 42, -inf)))
      ret ^= 1;
  return ret;
}
int main(void) {
  memset(dp, -1, sizeof(dp));
  scanf("%d", &N);
  for (int i = 0; i < N; ++i) scanf("%lf %lf", &P[i].first, &P[i].second);
  P[N] = P[0];
  for (int i = 0; i < N; ++i)
    for (int j = 0; j < i; ++j) {
      bool flag = true;
      for (int k = 0; k < N; ++k)
        if (k != j && i != k) {
          if (intersect(P[i], P[j], P[k], P[k + 1])) flag = false;
          if (on(P[k].first, P[k].second, P[i], P[j])) {
            flag = false;
          }
        }
      if (i - j != 1 && !inside((P[i].first + P[j].first) / 2.0,
                                (P[i].second + P[j].second) / 2.0))
        flag = false;
      ok[i][j] = ok[j][i] = flag;
    }
  printf("%d\n", f(0, N - 1));
  return 0;
}
