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 MN = 222;
const int MOD = 1e9 + 7;
long long operator*(pair<int, int> a, pair<int, int> b) {
  return a.first * (long long)b.second - a.second * (long long)b.first;
}
long long operator%(pair<int, int> a, pair<int, int> b) {
  return a.first * (long long)b.first + a.second * (long long)b.second;
}
pair<int, int> operator-(pair<int, int> a, pair<int, int> b) {
  return make_pair(a.first - b.first, a.second - b.second);
}
bool collinear(pair<int, int> a, pair<int, int> b, pair<int, int> c) {
  return (a - b) * (b - c) == 0;
}
int sign(long long a) {
  if (a > 0)
    return 1;
  else if (a == 0)
    return 0;
  else
    return -1;
}
bool splits(pair<int, int> a, pair<int, int> b, pair<int, int> c,
            pair<int, int> d) {
  return sign((a - b) * (a - c)) * sign((a - b) * (a - d)) != 1;
}
bool between(pair<int, int> a, pair<int, int> b, pair<int, int> c) {
  return (b - a) % (b - c) <= 0;
}
bool onsegment(pair<int, int> a, pair<int, int> b, pair<int, int> c) {
  return collinear(a, b, c) && between(a, b, c);
}
bool intersects(pair<int, int> a, pair<int, int> b, pair<int, int> c,
                pair<int, int> d) {
  if (collinear(a, b, d) && collinear(a, b, c))
    return between(a, c, b) || between(a, d, b) || between(c, a, d) ||
           between(c, b, d);
  else
    return splits(a, b, c, d) && splits(c, d, a, b);
}
bool isonray(pair<int, int> a, pair<int, int> b, pair<int, int> c) {
  bool ret = (a - b) * (a - c) == 0 && (a - b) % (a - c) >= 0;
  return ret;
}
bool good[MN][MN];
pair<int, int> polygon[MN];
int dp[MN][MN];
bool isinangle(pair<int, int> a, pair<int, int> b, pair<int, int> c,
               pair<int, int> x) {
  b = a - b;
  c = a - c;
  x = a - x;
  if (b * c >= 0)
    return b * x >= 0 && x * c >= 0;
  else
    return b * x >= 0 || x * c >= 0;
}
int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; ++i)
    scanf("%d%d", &polygon[i].first, &polygon[i].second);
  long long area = 0;
  for (int i = 1; i < n - 1; ++i)
    area += (polygon[0] - polygon[i]) * (polygon[0] - polygon[i + 1]);
  if (area > 0) reverse(polygon, polygon + n);
  for (int i = 0; i < n; ++i) good[i][i + 1] = true;
  for (int i = 0; i < n; ++i)
    for (int k = i + 2; k < n; ++k) {
      bool OK = true;
      if (isonray(polygon[i], polygon[(i + 1) % n], polygon[k]) ||
          isonray(polygon[i], polygon[(i + n - 1) % n], polygon[k]) ||
          isonray(polygon[k], polygon[(k + 1) % n], polygon[i]) ||
          isonray(polygon[k], polygon[(k + n - 1) % n], polygon[i])) {
        OK = false;
      }
      if (!isinangle(polygon[i], polygon[(i + n - 1) % n], polygon[(i + 1) % n],
                     polygon[k]))
        OK = false;
      if (!isinangle(polygon[k], polygon[(k + n - 1) % n], polygon[(k + 1) % n],
                     polygon[i]))
        OK = false;
      for (int l = 0; l < n; ++l)
        if (l != i && l != k && (l + 1) % n != i && (l + 1) % n != k)
          if (intersects(polygon[i], polygon[k], polygon[l],
                         polygon[(l + 1) % n])) {
            OK = false;
            break;
          }
      good[i][k] = good[k][i] = OK;
    }
  for (int i = 0; i < n - 1; ++i) dp[i][i + 1] = 1;
  for (int dist = 2; dist < n; ++dist)
    for (int i = 0; i + dist < n; ++i)
      for (int l = i + 1; l < i + dist; ++l)
        if (good[i][l] && good[l][i + dist])
          dp[i][i + dist] =
              (dp[i][i + dist] + (long long)dp[i][l] * dp[l][i + dist]) % MOD;
  printf("%d\n", dp[0][n - 1]);
}
