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;
template <class TH>
void _dbg(const char *sdbg, TH h) {
  cerr << sdbg << '=' << h << endl;
}
template <class TH, class... TA>
void _dbg(const char *sdbg, TH h, TA... a) {
  while (*sdbg != ',') cerr << *sdbg++;
  cerr << '=' << h << ',';
  _dbg(sdbg + 1, a...);
}
template <class L, class R>
ostream &operator<<(ostream &os, pair<L, R> p) {
  return os << "(" << p.first << ", " << p.second << ")";
}
template <class Iterable,
          class = typename enable_if<!is_same<string, Iterable>::value>::type>
auto operator<<(ostream &os, Iterable v) -> decltype(os << *begin(v)) {
  os << "[";
  for (auto vv : v) os << vv << ", ";
  return os << "]";
}
const int inf = 0x3f3f3f3f;
const long long infll = 0x3f3f3f3f3f3f3f3fll;
template <class T>
int sign(T x) {
  return (x > 0) - (x < 0);
}
template <class T>
struct point {
  T x, y;
  explicit point(T x = 0, T y = 0) : x(x), y(y) {}
  bool operator<(point<T> p) const { return tie(x, y) < tie(p.x, p.y); }
  bool operator==(point<T> p) const { return tie(x, y) == tie(p.x, p.y); }
  point<T> operator+(point<T> p) const { return point<T>(x + p.x, y + p.y); }
  point<T> operator-(point<T> p) const { return point<T>(x - p.x, y - p.y); }
  point<T> operator*(T d) const { return point<T>(x * d, y * d); }
  point<T> operator/(T d) const { return point<T>(x / d, y / d); }
  T dot(point<T> p) const { return x * p.x + y * p.y; }
  T cross(point<T> p) const { return x * p.y - y * p.x; }
  T cross(point<T> a, point<T> b) const { return (a - *this).cross(b - *this); }
  T dist2() const { return x * x + y * y; }
  double dist() const { return sqrt((double)dist2()); }
  double angle() const { return atan2(y, x); }
  point<T> unit() const { return *this / dist(); }
  point<T> perp() const { return point<T>(-y, x); }
  point<T> normal() const { return perp().unit(); }
  point<T> rotate(double a) const {
    return point<T>(x * cos(a) - y * sin(a), x * sin(a) + y * cos(a));
  }
};
template <class T>
point<T> linear_solve2(T a, T b, T c, T d, T e, T f) {
  point<T> retv;
  T det = a * d - b * c;
  return point<T>((e * d - f * b) / det, (a * f - c * e) / det);
}
template <class T>
struct segment {
  point<T> pi, pf;
  explicit segment(point<T> a, point<T> b) : pi(a), pf(b) {}
  double dist(point<T> p) {
    if (pi == pf) return (p - pi).dist();
    auto d = (pf - pi).dist2();
    auto t = min(d, max(.0, (p - pi).dot(pf - pi)));
    return ((p - pi) * d - (pf - pi) * t).dist() / d;
  }
  bool on_segment(point<T> p) {
    return p.cross(pi, pf) == 0 && (pi - p).dot(pf - p) <= 0;
  }
  vector<point<T> > intersect(segment rhs) {
    auto oa = rhs.pi.cross(rhs.pf, pi), ob = rhs.pi.cross(rhs.pf, pf),
         oc = pi.cross(pf, rhs.pi), od = pi.cross(pf, rhs.pf);
    if (sign(oa) * sign(ob) < 0 && sign(oc) * sign(od) < 0)
      return {(pi * ob - pf * oa) / (ob - oa)};
    set<point<T> > s;
    if (rhs.on_segment(pi)) s.insert(pi);
    if (rhs.on_segment(pf)) s.insert(pf);
    if (on_segment(rhs.pi)) s.insert(rhs.pi);
    if (on_segment(rhs.pf)) s.insert(rhs.pf);
    return vector<point<T> >(s.begin(), s.end());
  }
};
const long long mod = 1e9 + 7;
point<long long> p[212];
int n;
bool been[212][212];
long long tab[212][212];
long long polyside = 0;
long long pd(int l, int r) {
  if (been[l][r]) return tab[l][r];
  been[l][r] = true;
  bool ok = true;
  for (int k = 0; k < n; k++) {
    if (l != k && l != (k + 1) % n && r != k && r != (k + 1) % n) {
      segment<long long> s1 = segment<long long>(p[l], p[r]);
      segment<long long> s2 = segment<long long>(p[k], p[(k + 1) % n]);
      if (s2.intersect(s1).size()) {
        ok = false;
      }
    }
    if (l != k && r != k) {
      segment<long long> s1 = segment<long long>(p[l], p[r]);
      segment<long long> s2 = segment<long long>(p[k], p[k]);
      if (s2.intersect(s1).size()) {
        ok = false;
      }
    }
  }
  if (!ok) {
    return tab[l][r] = 0;
  }
  if (r - l <= 1) return tab[l][r] = 1;
  long long retv = 0;
  for (int i = l + 1; i < r; i++)
    if ((polyside * p[r].cross(p[l], p[(l + 1) % n]) <= 0 ||
         polyside * p[l].cross(p[(l + 1) % n], p[i]) >= 0) &&
        (polyside * p[(r - 1 + n) % n].cross(p[r], p[l]) <= 0 ||
         polyside * p[(r - 1 + n) % n].cross(p[r], p[i]) >= 0)) {
      if (polyside * p[r].cross(p[l], p[i]) >= 0)
        retv = (retv + pd(l, i) * pd(i, r)) % mod;
    }
  return tab[l][r] = retv;
}
int main(void) {
  cin >> n;
  for (int i = 0; i < n; i++) cin >> p[i].x >> p[i].y;
  point<long long> p0(0, 0);
  long long sum = 0;
  for (int i = 0; i < n; i++) sum += p0.cross(p[i], p[(i + 1) % n]);
  polyside = (sum > 0) ? 1 : -1;
  cout << pd(0, n - 1) << endl;
}
