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>
const int MAXN = 210;
const int mod = 1e9 + 7;
void reduce(int& x) { x += x >> 31 & mod; }
int mul(int x, int y) { return (long long)x * y % mod; }
void fma(int& x, int y, int z) { x = ((long long)y * z + x) % mod; }
struct vec {
  int x, y;
  vec() { x = y = 0; }
  vec(int a, int b) { x = a, y = b; }
  vec operator+(vec b) const { return vec(x + b.x, y + b.y); }
  vec operator-(vec b) const { return vec(x - b.x, y - b.y); }
  long long operator^(vec b) const {
    return (long long)x * b.y - (long long)y * b.x;
  }
  long long operator*(vec b) const {
    return (long long)x * b.x + (long long)y * b.y;
  }
  bool operator==(vec b) const { return x == b.x && y == b.y; }
} ps[MAXN];
int n;
long long cross(vec x, vec y, vec z) { return (y - x) ^ (z - x); }
inline int sgn(long long x) { return x < 0 ? -1 : x > 0; }
int dp[MAXN][MAXN];
int main() {
  std::ios_base::sync_with_stdio(false), std::cin.tie(0);
  std::cin >> n;
  for (int i = 1; i <= n; ++i) std::cin >> ps[i].x >> ps[i].y;
  long long area = 0;
  for (int i = 1; i <= n; ++i) area += ps[i] ^ ps[i == n ? 1 : i + 1];
  for (int i = 1; i < n; ++i) dp[i][i + 1] = 1;
  for (int L = 3; L <= n; ++L)
    for (int l = 1; l + L - 1 <= n; ++l) {
      int r = l + L - 1;
      for (int p = l + 1; p < r; ++p)
        if (sgn(cross(ps[p], ps[r], ps[l])) == sgn(area))
          fma(dp[l][r], dp[l][p], dp[p][r]);
    }
  std::cout << dp[1][n] << std::endl;
  return 0;
}
