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 MOD = 1000000007;
const int MAX = 205;
pair<long long, long long> p[MAX];
bool can[MAX][MAX];
long long dp[MAX][MAX], n;
int ccw(pair<long long, long long> a, pair<long long, long long> b,
        pair<long long, long long> c) {
  long long ans = (b.first - a.first) * (c.second - a.second) -
                  (b.second - a.second) * (c.first - a.first);
  if (ans < 0) ans = -1;
  if (ans > 0) ans = 1;
  return ans;
}
struct line {
  pair<long long, long long> p1, p2;
};
bool intersect(line l1, line l2) {
  int mn, mx;
  mn = min(l1.p1.first, l1.p2.first);
  mx = max(l1.p1.first, l1.p2.first);
  if (max(l2.p1.first, l2.p2.first) < mn) return false;
  if (min(l2.p1.first, l2.p2.first) > mx) return false;
  mn = min(l1.p1.second, l1.p2.second);
  mx = max(l1.p1.second, l1.p2.second);
  if (max(l2.p1.second, l2.p2.second) < mn) return false;
  if (min(l2.p1.second, l2.p2.second) > mx) return false;
  int t1 = ccw(l1.p1, l1.p2, l2.p1) * ccw(l1.p1, l1.p2, l2.p2);
  int t2 = ccw(l2.p1, l2.p2, l1.p1) * ccw(l2.p1, l2.p2, l1.p2);
  return (t1 <= 0 && t2 <= 0);
}
bool isinside(pair<long long, long long> a) {
  line ray;
  ray.p1 = a;
  ray.p2 = pair<long long, long long>(a.first - 1, 1000000000);
  int cnt = 0;
  for (int i = 0; i < n; i++) {
    line l;
    l.p1 = p[i];
    l.p2 = p[(i + 1) % n];
    cnt += intersect(ray, l);
    if (min(l.p1.first, l.p2.first) <= a.first &&
        a.first <= max(l.p1.first, l.p2.first))
      if (min(l.p1.second, l.p2.second) <= a.second &&
          a.second <= max(l.p1.second, l.p2.second))
        if (ccw(l.p1, l.p2, a) == 0) return false;
  }
  return cnt & 1;
}
bool isgood(line d) {
  int cnt = 0;
  for (int i = 0; i < n; i++) {
    line l;
    l.p1 = p[i];
    l.p2 = p[(i + 1) % n];
    cnt += intersect(l, d);
  }
  if (cnt != 4) return false;
  pair<long long, long long> mid((d.p1.first + d.p2.first) / 2,
                                 (d.p1.second + d.p2.second) / 2);
  return isinside(mid);
}
int main() {
  ios::sync_with_stdio(false);
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> p[i].first >> p[i].second;
    p[i].first *= 2;
    p[i].second *= 2;
  }
  if (n == 3) {
    cout << 1 << endl;
    return 0;
  }
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      if (i != j) {
        line l;
        l.p1 = p[i];
        l.p2 = p[j];
        can[i][j] = isgood(l);
      }
  for (int i = 0; i < n - 2; i++)
    if (can[i][i + 2]) dp[i][i + 3] = 1;
  for (int l = 4; l <= n; l++)
    for (int i = 0; i < n - l + 1; i++) {
      int j = i + l;
      if (can[j - 1][i + 1]) dp[i][j] += dp[i + 1][j];
      if (can[i][j - 2]) dp[i][j] += dp[i][j - 1];
      dp[i][j] %= MOD;
      for (int k = i; k < j; k++)
        if (can[i][k] && can[k][j - 1]) {
          dp[i][j] += dp[i][k + 1] * dp[k][j];
          dp[i][j] %= MOD;
        }
    }
  cout << dp[0][n] << endl;
  return 0;
}
