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;
struct point {
  double x, y;
  point operator-(const point& other) {
    return point(x - other.x, y - other.y);
  }
  double operator*(const point& b) { return x * b.y - y * b.x; }
  point(){};
  point(double xx, double yy) : x(xx), y(yy) {}
};
struct line {
  point a, b;
};
struct point3 {
  double x, y, z;
};
struct line3 {
  point3 a, b;
};
struct plane3 {
  point3 a, b, c;
};
int dots_onplane(point3 a, point3 b, point3 c, point3 d);
point3 subt(point3 u, point3 v);
double vlen(point3 p);
point3 pvec(plane3 s);
point3 pvec(point3 s1, point3 s2, point3 s3);
int dots_inline(point3 p1, point3 p2, point3 p3);
int dot_online_in(point3 p, line3 l);
int dot_online_in(point3 p, point3 l1, point3 l2);
double xmult(point p1, point p2, point p0) {
  return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);
}
double xmult(point p1, point p2) { return (p1.x) * (p2.y) - (p2.x) * (p1.y); }
point3 xmult(point3 u, point3 v) {
  point3 ret;
  ret.x = u.y * v.z - v.y * u.z;
  ret.y = u.z * v.x - u.x * v.z;
  ret.z = u.x * v.y - u.y * v.x;
  return ret;
}
double dmult(point3 u, point3 v) { return u.x * v.x + u.y * v.y + u.z * v.z; }
int dot_inplane_in(point3 p, plane3 s) {
  return (((vlen(xmult(subt(s.a, s.b), subt(s.a, s.c))) -
            vlen(xmult(subt(p, s.a), subt(p, s.b))) -
            vlen(xmult(subt(p, s.b), subt(p, s.c))) -
            vlen(xmult(subt(p, s.c), subt(p, s.a)))) > 0
               ? (vlen(xmult(subt(s.a, s.b), subt(s.a, s.c))) -
                  vlen(xmult(subt(p, s.a), subt(p, s.b))) -
                  vlen(xmult(subt(p, s.b), subt(p, s.c))) -
                  vlen(xmult(subt(p, s.c), subt(p, s.a))))
               : -(vlen(xmult(subt(s.a, s.b), subt(s.a, s.c))) -
                   vlen(xmult(subt(p, s.a), subt(p, s.b))) -
                   vlen(xmult(subt(p, s.b), subt(p, s.c))) -
                   vlen(xmult(subt(p, s.c), subt(p, s.a))))) < 1e-1);
}
int dot_inplane_in(point3 p, point3 s1, point3 s2, point3 s3) {
  return (((vlen(xmult(subt(s1, s2), subt(s1, s3))) -
            vlen(xmult(subt(p, s1), subt(p, s2))) -
            vlen(xmult(subt(p, s2), subt(p, s3))) -
            vlen(xmult(subt(p, s3), subt(p, s1)))) > 0
               ? (vlen(xmult(subt(s1, s2), subt(s1, s3))) -
                  vlen(xmult(subt(p, s1), subt(p, s2))) -
                  vlen(xmult(subt(p, s2), subt(p, s3))) -
                  vlen(xmult(subt(p, s3), subt(p, s1))))
               : -(vlen(xmult(subt(s1, s2), subt(s1, s3))) -
                   vlen(xmult(subt(p, s1), subt(p, s2))) -
                   vlen(xmult(subt(p, s2), subt(p, s3))) -
                   vlen(xmult(subt(p, s3), subt(p, s1))))) < 1e-1);
}
int dot_inplane_ex(point3 p, plane3 s) {
  return dot_inplane_in(p, s) &&
         vlen(xmult(subt(p, s.a), subt(p, s.b))) > 1e-1 &&
         vlen(xmult(subt(p, s.b), subt(p, s.c))) > 1e-1 &&
         vlen(xmult(subt(p, s.c), subt(p, s.a))) > 1e-1;
}
int dot_inplane_ex(point3 p, point3 s1, point3 s2, point3 s3) {
  return dot_inplane_in(p, s1, s2, s3) &&
         vlen(xmult(subt(p, s1), subt(p, s2))) > 1e-1 &&
         vlen(xmult(subt(p, s2), subt(p, s3))) > 1e-1 &&
         vlen(xmult(subt(p, s3), subt(p, s1))) > 1e-1;
}
int same_side(point3 p1, point3 p2, line3 l) {
  return dmult(xmult(subt(l.a, l.b), subt(p1, l.b)),
               xmult(subt(l.a, l.b), subt(p2, l.b))) > 1e-1;
}
int same_side(point3 p1, point3 p2, point3 l1, point3 l2) {
  return dmult(xmult(subt(l1, l2), subt(p1, l2)),
               xmult(subt(l1, l2), subt(p2, l2))) > 1e-1;
}
int opposite_side(point3 p1, point3 p2, line3 l) {
  return dmult(xmult(subt(l.a, l.b), subt(p1, l.b)),
               xmult(subt(l.a, l.b), subt(p2, l.b))) < -1e-1;
}
int opposite_side(point3 p1, point3 p2, point3 l1, point3 l2) {
  return dmult(xmult(subt(l1, l2), subt(p1, l2)),
               xmult(subt(l1, l2), subt(p2, l2))) < -1e-1;
}
int same_side(point3 p1, point3 p2, plane3 s) {
  return dmult(pvec(s), subt(p1, s.a)) * dmult(pvec(s), subt(p2, s.a)) > 1e-1;
}
int same_side(point3 p1, point3 p2, point3 s1, point3 s2, point3 s3) {
  return dmult(pvec(s1, s2, s3), subt(p1, s1)) *
             dmult(pvec(s1, s2, s3), subt(p2, s1)) >
         1e-1;
}
int opposite_side(point3 p1, point3 p2, plane3 s) {
  return dmult(pvec(s), subt(p1, s.a)) * dmult(pvec(s), subt(p2, s.a)) < -1e-1;
}
int opposite_side(point3 p1, point3 p2, point3 s1, point3 s2, point3 s3) {
  return dmult(pvec(s1, s2, s3), subt(p1, s1)) *
             dmult(pvec(s1, s2, s3), subt(p2, s1)) <
         -1e-1;
}
int parallel(line3 u, line3 v) {
  return vlen(xmult(subt(u.a, u.b), subt(v.a, v.b))) < 1e-1;
}
int parallel(point3 u1, point3 u2, point3 v1, point3 v2) {
  return vlen(xmult(subt(u1, u2), subt(v1, v2))) < 1e-1;
}
int parallel(plane3 u, plane3 v) {
  return vlen(xmult(pvec(u), pvec(v))) < 1e-1;
}
int parallel(point3 u1, point3 u2, point3 u3, point3 v1, point3 v2, point3 v3) {
  return vlen(xmult(pvec(u1, u2, u3), pvec(v1, v2, v3))) < 1e-1;
}
int parallel(line3 l, plane3 s) {
  return (((dmult(subt(l.a, l.b), pvec(s))) > 0
               ? (dmult(subt(l.a, l.b), pvec(s)))
               : -(dmult(subt(l.a, l.b), pvec(s)))) < 1e-1);
}
int parallel(point3 l1, point3 l2, point3 s1, point3 s2, point3 s3) {
  return (((dmult(subt(l1, l2), pvec(s1, s2, s3))) > 0
               ? (dmult(subt(l1, l2), pvec(s1, s2, s3)))
               : -(dmult(subt(l1, l2), pvec(s1, s2, s3)))) < 1e-1);
}
int perpendicular(line3 u, line3 v) {
  return (((dmult(subt(u.a, u.b), subt(v.a, v.b))) > 0
               ? (dmult(subt(u.a, u.b), subt(v.a, v.b)))
               : -(dmult(subt(u.a, u.b), subt(v.a, v.b)))) < 1e-1);
}
int perpendicular(point3 u1, point3 u2, point3 v1, point3 v2) {
  return (((dmult(subt(u1, u2), subt(v1, v2))) > 0
               ? (dmult(subt(u1, u2), subt(v1, v2)))
               : -(dmult(subt(u1, u2), subt(v1, v2)))) < 1e-1);
}
int perpendicular(plane3 u, plane3 v) {
  return (((dmult(pvec(u), pvec(v))) > 0 ? (dmult(pvec(u), pvec(v)))
                                         : -(dmult(pvec(u), pvec(v)))) < 1e-1);
}
int perpendicular(point3 u1, point3 u2, point3 u3, point3 v1, point3 v2,
                  point3 v3) {
  return (((dmult(pvec(u1, u2, u3), pvec(v1, v2, v3))) > 0
               ? (dmult(pvec(u1, u2, u3), pvec(v1, v2, v3)))
               : -(dmult(pvec(u1, u2, u3), pvec(v1, v2, v3)))) < 1e-1);
}
int perpendicular(line3 l, plane3 s) {
  return vlen(xmult(subt(l.a, l.b), pvec(s))) < 1e-1;
}
int perpendicular(point3 l1, point3 l2, point3 s1, point3 s2, point3 s3) {
  return vlen(xmult(subt(l1, l2), pvec(s1, s2, s3))) < 1e-1;
}
int intersect_in(line3 u, line3 v) {
  if (!dots_onplane(u.a, u.b, v.a, v.b)) return 0;
  if (!dots_inline(u.a, u.b, v.a) || !dots_inline(u.a, u.b, v.b))
    return !same_side(u.a, u.b, v) && !same_side(v.a, v.b, u);
  return dot_online_in(u.a, v) || dot_online_in(u.b, v) ||
         dot_online_in(v.a, u) || dot_online_in(v.b, u);
}
int intersect_in(point3 u1, point3 u2, point3 v1, point3 v2) {
  if (!dots_onplane(u1, u2, v1, v2)) return 0;
  if (!dots_inline(u1, u2, v1) || !dots_inline(u1, u2, v2))
    return !same_side(u1, u2, v1, v2) && !same_side(v1, v2, u1, u2);
  return dot_online_in(u1, v1, v2) || dot_online_in(u2, v1, v2) ||
         dot_online_in(v1, u1, u2) || dot_online_in(v2, u1, u2);
}
int intersect_ex(line3 u, line3 v) {
  return dots_onplane(u.a, u.b, v.a, v.b) && opposite_side(u.a, u.b, v) &&
         opposite_side(v.a, v.b, u);
}
int intersect_ex(point3 u1, point3 u2, point3 v1, point3 v2) {
  return dots_onplane(u1, u2, v1, v2) && opposite_side(u1, u2, v1, v2) &&
         opposite_side(v1, v2, u1, u2);
}
point3 subt(point3 u, point3 v) {
  point3 ret;
  ret.x = u.x - v.x;
  ret.y = u.y - v.y;
  ret.z = u.z - v.z;
  return ret;
}
point3 pvec(plane3 s) { return xmult(subt(s.a, s.b), subt(s.b, s.c)); }
point3 pvec(point3 s1, point3 s2, point3 s3) {
  return xmult(subt(s1, s2), subt(s2, s3));
}
double Distance(point3 p1, point3 p2) {
  return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y) +
              (p1.z - p2.z) * (p1.z - p2.z));
}
double vlen(point3 p) { return sqrt(p.x * p.x + p.y * p.y + p.z * p.z); }
int dots_inline(point3 p1, point3 p2, point3 p3) {
  return vlen(xmult(subt(p1, p2), subt(p2, p3))) < 1e-1;
}
int dots_onplane(point3 a, point3 b, point3 c, point3 d) {
  return (((dmult(pvec(a, b, c), subt(d, a))) > 0
               ? (dmult(pvec(a, b, c), subt(d, a)))
               : -(dmult(pvec(a, b, c), subt(d, a)))) < 1e-1);
}
int dot_online_in(point3 p, line3 l) {
  return (((vlen(xmult(subt(p, l.a), subt(p, l.b)))) > 0
               ? (vlen(xmult(subt(p, l.a), subt(p, l.b))))
               : -(vlen(xmult(subt(p, l.a), subt(p, l.b))))) < 1e-1) &&
         (l.a.x - p.x) * (l.b.x - p.x) < 1e-1 &&
         (l.a.y - p.y) * (l.b.y - p.y) < 1e-1 &&
         (l.a.z - p.z) * (l.b.z - p.z) < 1e-1;
}
int dot_online_in(point3 p, point3 l1, point3 l2) {
  return (((vlen(xmult(subt(p, l1), subt(p, l2)))) > 0
               ? (vlen(xmult(subt(p, l1), subt(p, l2))))
               : -(vlen(xmult(subt(p, l1), subt(p, l2))))) < 1e-1) &&
         (l1.x - p.x) * (l2.x - p.x) < 1e-1 &&
         (l1.y - p.y) * (l2.y - p.y) < 1e-1 &&
         (l1.z - p.z) * (l2.z - p.z) < 1e-1;
}
int dot_online_ex(point3 p, line3 l) {
  return dot_online_in(p, l) &&
         (!(((p.x - l.a.x) > 0 ? (p.x - l.a.x) : -(p.x - l.a.x)) < 1e-1) ||
          !(((p.y - l.a.y) > 0 ? (p.y - l.a.y) : -(p.y - l.a.y)) < 1e-1) ||
          !(((p.z - l.a.z) > 0 ? (p.z - l.a.z) : -(p.z - l.a.z)) < 1e-1)) &&
         (!(((p.x - l.b.x) > 0 ? (p.x - l.b.x) : -(p.x - l.b.x)) < 1e-1) ||
          !(((p.y - l.b.y) > 0 ? (p.y - l.b.y) : -(p.y - l.b.y)) < 1e-1) ||
          !(((p.z - l.b.z) > 0 ? (p.z - l.b.z) : -(p.z - l.b.z)) < 1e-1));
}
int dot_online_ex(point3 p, point3 l1, point3 l2) {
  return dot_online_in(p, l1, l2) &&
         (!(((p.x - l1.x) > 0 ? (p.x - l1.x) : -(p.x - l1.x)) < 1e-1) ||
          !(((p.y - l1.y) > 0 ? (p.y - l1.y) : -(p.y - l1.y)) < 1e-1) ||
          !(((p.z - l1.z) > 0 ? (p.z - l1.z) : -(p.z - l1.z)) < 1e-1)) &&
         (!(((p.x - l2.x) > 0 ? (p.x - l2.x) : -(p.x - l2.x)) < 1e-1) ||
          !(((p.y - l2.y) > 0 ? (p.y - l2.y) : -(p.y - l2.y)) < 1e-1) ||
          !(((p.z - l2.z) > 0 ? (p.z - l2.z) : -(p.z - l2.z)) < 1e-1));
}
int intersect_in(line3 l, plane3 s) {
  return !same_side(l.a, l.b, s) && !same_side(s.a, s.b, l.a, l.b, s.c) &&
         !same_side(s.b, s.c, l.a, l.b, s.a) &&
         !same_side(s.c, s.a, l.a, l.b, s.b);
}
int intersect_in(point3 l1, point3 l2, point3 s1, point3 s2, point3 s3) {
  return !same_side(l1, l2, s1, s2, s3) && !same_side(s1, s2, l1, l2, s3) &&
         !same_side(s2, s3, l1, l2, s1) && !same_side(s3, s1, l1, l2, s2);
}
int intersect_ex(line3 l, plane3 s) {
  return opposite_side(l.a, l.b, s) && opposite_side(s.a, s.b, l.a, l.b, s.c) &&
         opposite_side(s.b, s.c, l.a, l.b, s.a) &&
         opposite_side(s.c, s.a, l.a, l.b, s.b);
}
int intersect_ex(point3 l1, point3 l2, point3 s1, point3 s2, point3 s3) {
  return opposite_side(l1, l2, s1, s2, s3) &&
         opposite_side(s1, s2, l1, l2, s3) &&
         opposite_side(s2, s3, l1, l2, s1) && opposite_side(s3, s1, l1, l2, s2);
}
point3 intersection(line3 u, line3 v) {
  point3 ret = u.a;
  double t =
      ((u.a.x - v.a.x) * (v.a.y - v.b.y) - (u.a.y - v.a.y) * (v.a.x - v.b.x)) /
      ((u.a.x - u.b.x) * (v.a.y - v.b.y) - (u.a.y - u.b.y) * (v.a.x - v.b.x));
  ret.x += (u.b.x - u.a.x) * t;
  ret.y += (u.b.y - u.a.y) * t;
  ret.z += (u.b.z - u.a.z) * t;
  return ret;
}
point3 intersection(point3 u1, point3 u2, point3 v1, point3 v2) {
  point3 ret = u1;
  double t = ((u1.x - v1.x) * (v1.y - v2.y) - (u1.y - v1.y) * (v1.x - v2.x)) /
             ((u1.x - u2.x) * (v1.y - v2.y) - (u1.y - u2.y) * (v1.x - v2.x));
  ret.x += (u2.x - u1.x) * t;
  ret.y += (u2.y - u1.y) * t;
  ret.z += (u2.z - u1.z) * t;
  return ret;
}
point3 intersection(line3 l, plane3 s) {
  point3 ret = pvec(s);
  double t = (ret.x * (s.a.x - l.a.x) + ret.y * (s.a.y - l.a.y) +
              ret.z * (s.a.z - l.a.z)) /
             (ret.x * (l.b.x - l.a.x) + ret.y * (l.b.y - l.a.y) +
              ret.z * (l.b.z - l.a.z));
  ret.x = l.a.x + (l.b.x - l.a.x) * t;
  ret.y = l.a.y + (l.b.y - l.a.y) * t;
  ret.z = l.a.z + (l.b.z - l.a.z) * t;
  return ret;
}
point3 intersection(point3 l1, point3 l2, point3 s1, point3 s2, point3 s3) {
  point3 ret = pvec(s1, s2, s3);
  double t =
      (ret.x * (s1.x - l1.x) + ret.y * (s1.y - l1.y) + ret.z * (s1.z - l1.z)) /
      (ret.x * (l2.x - l1.x) + ret.y * (l2.y - l1.y) + ret.z * (l2.z - l1.z));
  ret.x = l1.x + (l2.x - l1.x) * t;
  ret.y = l1.y + (l2.y - l1.y) * t;
  ret.z = l1.z + (l2.z - l1.z) * t;
  return ret;
}
line3 intersection(plane3 u, plane3 v) {
  line3 ret;
  ret.a = parallel(v.a, v.b, u.a, u.b, u.c)
              ? intersection(v.b, v.c, u.a, u.b, u.c)
              : intersection(v.a, v.b, u.a, u.b, u.c);
  ret.b = parallel(v.c, v.a, u.a, u.b, u.c)
              ? intersection(v.b, v.c, u.a, u.b, u.c)
              : intersection(v.c, v.a, u.a, u.b, u.c);
  return ret;
}
line3 intersection(point3 u1, point3 u2, point3 u3, point3 v1, point3 v2,
                   point3 v3) {
  line3 ret;
  ret.a = parallel(v1, v2, u1, u2, u3) ? intersection(v2, v3, u1, u2, u3)
                                       : intersection(v1, v2, u1, u2, u3);
  ret.b = parallel(v3, v1, u1, u2, u3) ? intersection(v2, v3, u1, u2, u3)
                                       : intersection(v3, v1, u1, u2, u3);
  return ret;
}
double ptoline(point3 p, line3 l) {
  return vlen(xmult(subt(p, l.a), subt(l.b, l.a))) / Distance(l.a, l.b);
}
double ptoline(point3 p, point3 l1, point3 l2) {
  return vlen(xmult(subt(p, l1), subt(l2, l1))) / Distance(l1, l2);
}
double ptoplane(point3 p, plane3 s) {
  return fabs(dmult(pvec(s), subt(p, s.a))) / vlen(pvec(s));
}
double ptoplane(point3 p, point3 s1, point3 s2, point3 s3) {
  return fabs(dmult(pvec(s1, s2, s3), subt(p, s1))) / vlen(pvec(s1, s2, s3));
}
double linetoline(line3 u, line3 v) {
  point3 n = xmult(subt(u.a, u.b), subt(v.a, v.b));
  return fabs(dmult(subt(u.a, v.a), n)) / vlen(n);
}
double linetoline(point3 u1, point3 u2, point3 v1, point3 v2) {
  point3 n = xmult(subt(u1, u2), subt(v1, v2));
  return fabs(dmult(subt(u1, v1), n)) / vlen(n);
}
double angle_cos(line3 u, line3 v) {
  return dmult(subt(u.a, u.b), subt(v.a, v.b)) / vlen(subt(u.a, u.b)) /
         vlen(subt(v.a, v.b));
}
double angle_cos(point3 u1, point3 u2, point3 v1, point3 v2) {
  return dmult(subt(u1, u2), subt(v1, v2)) / vlen(subt(u1, u2)) /
         vlen(subt(v1, v2));
}
double angle_cos(plane3 u, plane3 v) {
  return dmult(pvec(u), pvec(v)) / vlen(pvec(u)) / vlen(pvec(v));
}
double angle_cos(point3 u1, point3 u2, point3 u3, point3 v1, point3 v2,
                 point3 v3) {
  return dmult(pvec(u1, u2, u3), pvec(v1, v2, v3)) / vlen(pvec(u1, u2, u3)) /
         vlen(pvec(v1, v2, v3));
}
double angle_sin(line3 l, plane3 s) {
  return dmult(subt(l.a, l.b), pvec(s)) / vlen(subt(l.a, l.b)) / vlen(pvec(s));
}
double angle_sin(point3 l1, point3 l2, point3 s1, point3 s2, point3 s3) {
  return dmult(subt(l1, l2), pvec(s1, s2, s3)) / vlen(subt(l1, l2)) /
         vlen(pvec(s1, s2, s3));
}
point p1, p2;
int graham_cp(const void* a, const void* b) {
  double ret = xmult(*((point*)a), *((point*)b), p1);
  return (((ret) > 0 ? (ret) : -(ret)) < 1e-1)
             ? (xmult(*((point*)a), *((point*)b), p2) > 0 ? 1 : -1)
             : (ret > 0 ? 1 : -1);
}
void _graham(int n, point* p, int& s, point* ch) {
  int i, k = 0;
  for (p1 = p2 = p[0], i = 1; i < n; p2.x += p[i].x, p2.y += p[i].y, i++)
    if (p1.y - p[i].y > 1e-1 ||
        ((((p1.y - p[i].y) > 0 ? (p1.y - p[i].y) : -(p1.y - p[i].y)) < 1e-1) &&
         p1.x > p[i].x))
      p1 = p[k = i];
  p2.x /= n, p2.y /= n;
  p[k] = p[0], p[0] = p1;
  qsort(p + 1, n - 1, sizeof(point), graham_cp);
  for (ch[0] = p[0], ch[1] = p[1], ch[2] = p[2], s = i = 3; i < n;
       ch[s++] = p[i++])
    for (; s > 2 && xmult(ch[s - 2], p[i], ch[s - 1]) < -1e-1; s--)
      ;
}
int graham(int n, point* p, point* convex, int maxsize = 1, int dir = 1) {
  point* temp = new point[n];
  int s, i;
  _graham(n, p, s, temp);
  for (convex[0] = temp[0], n = 1, i = (dir ? 1 : (s - 1)); dir ? (i < s) : i;
       i += (dir ? 1 : -1))
    if (maxsize ||
        !(((xmult(temp[i - 1], temp[i], temp[(i + 1) % s])) > 0
               ? (xmult(temp[i - 1], temp[i], temp[(i + 1) % s]))
               : -(xmult(temp[i - 1], temp[i], temp[(i + 1) % s]))) < 1e-1))
      convex[n++] = temp[i];
  delete[] temp;
  return n;
}
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int grid_onedge(int n, point* p) {
  int i, ret = 0;
  for (i = 0; i < n; i++)
    ret +=
        gcd(((p[i].x - p[(i + 1) % n].x) > 0 ? (p[i].x - p[(i + 1) % n].x)
                                             : -(p[i].x - p[(i + 1) % n].x)),
            ((p[i].y - p[(i + 1) % n].y) > 0 ? (p[i].y - p[(i + 1) % n].y)
                                             : -(p[i].y - p[(i + 1) % n].y)));
  return ret;
}
int grid_inside(int n, point* p) {
  int i, ret = 0;
  for (i = 0; i < n; i++) ret += p[(i + 1) % n].y * (p[i].x - p[(i + 2) % n].x);
  return (((ret) > 0 ? (ret) : -(ret)) - grid_onedge(n, p)) / 2 + 1;
}
double Distance(point p1, point p2) {
  return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
}
double disptoline(point p, point l1, point l2) {
  return fabs(xmult(p, l1, l2)) / Distance(l1, l2);
}
point intersection(point u1, point u2, point v1, point v2) {
  point ret = u1;
  double t = ((u1.x - v1.x) * (v1.y - v2.y) - (u1.y - v1.y) * (v1.x - v2.x)) /
             ((u1.x - u2.x) * (v1.y - v2.y) - (u1.y - u2.y) * (v1.x - v2.x));
  ret.x += (u2.x - u1.x) * t;
  ret.y += (u2.y - u1.y) * t;
  return ret;
}
int intersect_line_circle(point c, double r, point l1, point l2) {
  return disptoline(c, l1, l2) < r + 1e-1;
}
int intersect_seg_circle(point c, double r, point l1, point l2) {
  double t1 = Distance(c, l1) - r, t2 = Distance(c, l2) - r;
  point t = c;
  if (t1 < 1e-1 || t2 < 1e-1) return t1 > -1e-1 || t2 > -1e-1;
  t.x += l1.y - l2.y;
  t.y += l2.x - l1.x;
  return xmult(l1, c, t) * xmult(l2, c, t) < 1e-1 &&
         disptoline(c, l1, l2) - r < 1e-1;
}
int intersect_circle_circle(point c1, double r1, point c2, double r2) {
  return Distance(c1, c2) < r1 + r2 + 1e-1 &&
         Distance(c1, c2) > fabs(r1 - r2) - 1e-1;
}
point dot_to_circle(point c, double r, point p) {
  point u, v;
  if (Distance(p, c) < 1e-1) return p;
  u.x = c.x + r * fabs(c.x - p.x) / Distance(c, p);
  u.y = c.y + r * fabs(c.y - p.y) / Distance(c, p) *
                  ((c.x - p.x) * (c.y - p.y) < 0 ? -1 : 1);
  v.x = c.x - r * fabs(c.x - p.x) / Distance(c, p);
  v.y = c.y - r * fabs(c.y - p.y) / Distance(c, p) *
                  ((c.x - p.x) * (c.y - p.y) < 0 ? -1 : 1);
  return Distance(u, p) < Distance(v, p) ? u : v;
}
void intersection_line_circle(point c, double r, point l1, point l2, point& p1,
                              point& p2) {
  point p = c;
  double t;
  p.x += l1.y - l2.y;
  p.y += l2.x - l1.x;
  p = intersection(p, c, l1, l2);
  t = sqrt(r * r - Distance(p, c) * Distance(p, c)) / Distance(l1, l2);
  p1.x = p.x + (l2.x - l1.x) * t;
  p1.y = p.y + (l2.y - l1.y) * t;
  p2.x = p.x - (l2.x - l1.x) * t;
  p2.y = p.y - (l2.y - l1.y) * t;
}
void intersection_circle_circle(point c1, double r1, point c2, double r2,
                                point& p1, point& p2) {
  point u, v;
  double t;
  t = (1 + (r1 * r1 - r2 * r2) / Distance(c1, c2) / Distance(c1, c2)) / 2;
  u.x = c1.x + (c2.x - c1.x) * t;
  u.y = c1.y + (c2.y - c1.y) * t;
  v.x = u.x + c1.y - c2.y;
  v.y = u.y - c1.x + c2.x;
  intersection_line_circle(c1, r1, u, v, p1, p2);
}
int xmult_int(point p1, point p2, point p0) {
  return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);
}
int xmult(int x1, int y1, int x2, int y2, int x0, int y0) {
  return (x1 - x0) * (y2 - y0) - (x2 - x0) * (y1 - y0);
}
int dmult_int(point p1, point p2, point p0) {
  return (p1.x - p0.x) * (p2.x - p0.x) + (p1.y - p0.y) * (p2.y - p0.y);
}
int dmult(int x1, int y1, int x2, int y2, int x0, int y0) {
  return (x1 - x0) * (x2 - x0) + (y1 - y0) * (y2 - y0);
}
int dots_inline(int x1, int y1, int x2, int y2, int x3, int y3) {
  return !xmult(x1, y1, x2, y2, x3, y3);
}
int dot_online_in(int x, int y, int x1, int y1, int x2, int y2) {
  return !xmult(x, y, x1, y1, x2, y2) && (x1 - x) * (x2 - x) <= 0 &&
         (y1 - y) * (y2 - y) <= 0;
}
int dot_online_ex(int x, int y, int x1, int y1, int x2, int y2) {
  return dot_online_in(x, y, x1, y1, x2, y2) && (x != x1 || y != y1) &&
         (x != x2 || y != y2);
}
int is_convex(int n, point* p) {
  int i, s[3] = {1, 1, 1};
  for (i = 0; i < n && s[1] | s[2]; i++)
    s[((xmult(p[(i + 1) % n], p[(i + 2) % n], p[i])) > 1e-1
           ? 1
           : ((xmult(p[(i + 1) % n], p[(i + 2) % n], p[i])) < -1e-1 ? 2 : 0))] =
        0;
  return s[1] | s[2];
}
int is_convex_v2(int n, point* p) {
  int i, s[3] = {1, 1, 1};
  for (i = 0; i < n && s[0] && s[1] | s[2]; i++)
    s[((xmult(p[(i + 1) % n], p[(i + 2) % n], p[i])) > 1e-1
           ? 1
           : ((xmult(p[(i + 1) % n], p[(i + 2) % n], p[i])) < -1e-1 ? 2 : 0))] =
        0;
  return s[0] && s[1] | s[2];
}
int inside_convex(point q, int n, point* p) {
  int i, s[3] = {1, 1, 1};
  for (i = 0; i < n && s[1] | s[2]; i++)
    s[((xmult(p[(i + 1) % n], q, p[i])) > 1e-1
           ? 1
           : ((xmult(p[(i + 1) % n], q, p[i])) < -1e-1 ? 2 : 0))] = 0;
  return s[1] | s[2];
}
int inside_convex_v2(point q, int n, point* p) {
  int i, s[3] = {1, 1, 1};
  for (i = 0; i < n && s[0] && s[1] | s[2]; i++)
    s[((xmult(p[(i + 1) % n], q, p[i])) > 1e-1
           ? 1
           : ((xmult(p[(i + 1) % n], q, p[i])) < -1e-1 ? 2 : 0))] = 0;
  return s[0] && s[1] | s[2];
}
int inside_polygon(point q, int n, point* p, int on_edge = 1) {
  point q2;
  int i = 0, count;
  while (i < n)
    for (count = i = 0, q2.x = rand() + 10000, q2.y = rand() + 10000; i < n;
         i++)
      if ((((xmult(q, p[i], p[(i + 1) % n])) > 0
                ? (xmult(q, p[i], p[(i + 1) % n]))
                : -(xmult(q, p[i], p[(i + 1) % n]))) < 1e-1) &&
          (p[i].x - q.x) * (p[(i + 1) % n].x - q.x) < 1e-1 &&
          (p[i].y - q.y) * (p[(i + 1) % n].y - q.y) < 1e-1)
        return on_edge;
      else if ((((xmult(q, q2, p[i])) > 0 ? (xmult(q, q2, p[i]))
                                          : -(xmult(q, q2, p[i]))) < 1e-1))
        break;
      else if (xmult(q, p[i], q2) * xmult(q, p[(i + 1) % n], q2) < -1e-1 &&
               xmult(p[i], q, p[(i + 1) % n]) *
                       xmult(p[i], q2, p[(i + 1) % n]) <
                   -1e-1)
        count++;
  return count & 1;
}
inline int opposite_side(point p1, point p2, point l1, point l2) {
  return xmult(l1, p1, l2) * xmult(l1, p2, l2) < -1e-1;
}
inline int dot_online_in(point p, point l1, point l2) {
  return (((xmult(p, l1, l2)) > 0 ? (xmult(p, l1, l2)) : -(xmult(p, l1, l2))) <
          1e-1) &&
         (l1.x - p.x) * (l2.x - p.x) < 1e-1 &&
         (l1.y - p.y) * (l2.y - p.y) < 1e-1;
}
bool inside_polygon(point l1, point l2, int n, point* p) {
  point t[401], tt;
  int i, j, k = 0;
  if (!inside_polygon(l1, n, p) || !inside_polygon(l2, n, p)) return false;
  for (i = 0; i < n; i++)
    if (opposite_side(l1, l2, p[i], p[(i + 1) % n]) &&
        opposite_side(p[i], p[(i + 1) % n], l1, l2))
      return false;
    else if (dot_online_in(l1, p[i], p[(i + 1) % n]))
      t[k++] = l1;
    else if (dot_online_in(l2, p[i], p[(i + 1) % n]))
      t[k++] = l2;
    else if (dot_online_in(p[i], l1, l2))
      t[k++] = p[i];
  for (i = 0; i < k; i++)
    for (j = i + 1; j < k; j++) {
      tt.x = (t[i].x + t[j].x) / 2;
      tt.y = (t[i].y + t[j].y) / 2;
      if (!inside_polygon(tt, n, p)) return false;
    }
  return true;
}
point intersection(line u, line v) {
  point ret = u.a;
  double t =
      ((u.a.x - v.a.x) * (v.a.y - v.b.y) - (u.a.y - v.a.y) * (v.a.x - v.b.x)) /
      ((u.a.x - u.b.x) * (v.a.y - v.b.y) - (u.a.y - u.b.y) * (v.a.x - v.b.x));
  ret.x += (u.b.x - u.a.x) * t;
  ret.y += (u.b.y - u.a.y) * t;
  return ret;
}
int same_side(point p1, point p2, point l1, point l2) {
  return xmult(l1, p1, l2) * xmult(l1, p2, l2) > 1e-1;
}
void polygon_cut(int& n, point* p, point l1, point l2, point side) {
  point pp[100];
  int m = 0, i;
  for (i = 0; i < n; i++) {
    if (same_side(p[i], side, l1, l2)) pp[m++] = p[i];
    if (!same_side(p[i], p[(i + 1) % n], l1, l2) &&
        !((((xmult(p[i], l1, l2)) > 0 ? (xmult(p[i], l1, l2))
                                      : -(xmult(p[i], l1, l2))) < 1e-1) &&
          (((xmult(p[(i + 1) % n], l1, l2)) > 0
                ? (xmult(p[(i + 1) % n], l1, l2))
                : -(xmult(p[(i + 1) % n], l1, l2))) < 1e-1)))
      pp[m++] = intersection(p[i], p[(i + 1) % n], l1, l2);
  }
  for (n = i = 0; i < m; i++)
    if (!i ||
        !(((pp[i].x - pp[i - 1].x) > 0 ? (pp[i].x - pp[i - 1].x)
                                       : -(pp[i].x - pp[i - 1].x)) < 1e-1) ||
        !(((pp[i].y - pp[i - 1].y) > 0 ? (pp[i].y - pp[i - 1].y)
                                       : -(pp[i].y - pp[i - 1].y)) < 1e-1))
      p[n++] = pp[i];
  if ((((p[n - 1].x - p[0].x) > 0 ? (p[n - 1].x - p[0].x)
                                  : -(p[n - 1].x - p[0].x)) < 1e-1) &&
      (((p[n - 1].y - p[0].y) > 0 ? (p[n - 1].y - p[0].y)
                                  : -(p[n - 1].y - p[0].y)) < 1e-1))
    n--;
  if (n < 3) n = 0;
}
double xmult(double x1, double y1, double x2, double y2, double x0, double y0) {
  return (x1 - x0) * (y2 - y0) - (x2 - x0) * (y1 - y0);
}
double dmult(point p1, point p2, point p0) {
  return (p1.x - p0.x) * (p2.x - p0.x) + (p1.y - p0.y) * (p2.y - p0.y);
}
double dmult(double x1, double y1, double x2, double y2, double x0, double y0) {
  return (x1 - x0) * (x2 - x0) + (y1 - y0) * (y2 - y0);
}
double Distance(double x1, double y1, double x2, double y2) {
  return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
int dots_inline(point p1, point p2, point p3) {
  return (((xmult(p1, p2, p3)) > 0 ? (xmult(p1, p2, p3))
                                   : -(xmult(p1, p2, p3))) < 1e-1);
}
int dots_inline(double x1, double y1, double x2, double y2, double x3,
                double y3) {
  return (((xmult(x1, y1, x2, y2, x3, y3)) > 0
               ? (xmult(x1, y1, x2, y2, x3, y3))
               : -(xmult(x1, y1, x2, y2, x3, y3))) < 1e-1);
}
int dot_online_in(point p, line l) {
  return (((xmult(p, l.a, l.b)) > 0 ? (xmult(p, l.a, l.b))
                                    : -(xmult(p, l.a, l.b))) < 1e-1) &&
         (l.a.x - p.x) * (l.b.x - p.x) < 1e-1 &&
         (l.a.y - p.y) * (l.b.y - p.y) < 1e-1;
}
int dot_online_in(double x, double y, double x1, double y1, double x2,
                  double y2) {
  return (((xmult(x, y, x1, y1, x2, y2)) > 0
               ? (xmult(x, y, x1, y1, x2, y2))
               : -(xmult(x, y, x1, y1, x2, y2))) < 1e-1) &&
         (x1 - x) * (x2 - x) < 1e-1 && (y1 - y) * (y2 - y) < 1e-1;
}
int dot_online_ex(point p, line l) {
  return dot_online_in(p, l) &&
         (!(((p.x - l.a.x) > 0 ? (p.x - l.a.x) : -(p.x - l.a.x)) < 1e-1) ||
          !(((p.y - l.a.y) > 0 ? (p.y - l.a.y) : -(p.y - l.a.y)) < 1e-1)) &&
         (!(((p.x - l.b.x) > 0 ? (p.x - l.b.x) : -(p.x - l.b.x)) < 1e-1) ||
          !(((p.y - l.b.y) > 0 ? (p.y - l.b.y) : -(p.y - l.b.y)) < 1e-1));
}
int dot_online_ex(point p, point l1, point l2) {
  return dot_online_in(p, l1, l2) &&
         (!(((p.x - l1.x) > 0 ? (p.x - l1.x) : -(p.x - l1.x)) < 1e-1) ||
          !(((p.y - l1.y) > 0 ? (p.y - l1.y) : -(p.y - l1.y)) < 1e-1)) &&
         (!(((p.x - l2.x) > 0 ? (p.x - l2.x) : -(p.x - l2.x)) < 1e-1) ||
          !(((p.y - l2.y) > 0 ? (p.y - l2.y) : -(p.y - l2.y)) < 1e-1));
}
int dot_online_ex(double x, double y, double x1, double y1, double x2,
                  double y2) {
  return dot_online_in(x, y, x1, y1, x2, y2) &&
         (!(((x - x1) > 0 ? (x - x1) : -(x - x1)) < 1e-1) ||
          !(((y - y1) > 0 ? (y - y1) : -(y - y1)) < 1e-1)) &&
         (!(((x - x2) > 0 ? (x - x2) : -(x - x2)) < 1e-1) ||
          !(((y - y2) > 0 ? (y - y2) : -(y - y2)) < 1e-1));
}
int same_side(point p1, point p2, line l) {
  return xmult(l.a, p1, l.b) * xmult(l.a, p2, l.b) > 1e-1;
}
int opposite_side(point p1, point p2, line l) {
  return xmult(l.a, p1, l.b) * xmult(l.a, p2, l.b) < -1e-1;
}
int parallel(line u, line v) {
  return ((((u.a.x - u.b.x) * (v.a.y - v.b.y) -
            (v.a.x - v.b.x) * (u.a.y - u.b.y)) > 0
               ? ((u.a.x - u.b.x) * (v.a.y - v.b.y) -
                  (v.a.x - v.b.x) * (u.a.y - u.b.y))
               : -((u.a.x - u.b.x) * (v.a.y - v.b.y) -
                   (v.a.x - v.b.x) * (u.a.y - u.b.y))) < 1e-1);
}
int parallel(point u1, point u2, point v1, point v2) {
  return ((((u1.x - u2.x) * (v1.y - v2.y) - (v1.x - v2.x) * (u1.y - u2.y)) > 0
               ? ((u1.x - u2.x) * (v1.y - v2.y) - (v1.x - v2.x) * (u1.y - u2.y))
               : -((u1.x - u2.x) * (v1.y - v2.y) -
                   (v1.x - v2.x) * (u1.y - u2.y))) < 1e-1);
}
int perpendicular(line u, line v) {
  return ((((u.a.x - u.b.x) * (v.a.x - v.b.x) +
            (u.a.y - u.b.y) * (v.a.y - v.b.y)) > 0
               ? ((u.a.x - u.b.x) * (v.a.x - v.b.x) +
                  (u.a.y - u.b.y) * (v.a.y - v.b.y))
               : -((u.a.x - u.b.x) * (v.a.x - v.b.x) +
                   (u.a.y - u.b.y) * (v.a.y - v.b.y))) < 1e-1);
}
int perpendicular(point u1, point u2, point v1, point v2) {
  return ((((u1.x - u2.x) * (v1.x - v2.x) + (u1.y - u2.y) * (v1.y - v2.y)) > 0
               ? ((u1.x - u2.x) * (v1.x - v2.x) + (u1.y - u2.y) * (v1.y - v2.y))
               : -((u1.x - u2.x) * (v1.x - v2.x) +
                   (u1.y - u2.y) * (v1.y - v2.y))) < 1e-1);
}
int intersect_in(line u, line v) {
  if (!dots_inline(u.a, u.b, v.a) || !dots_inline(u.a, u.b, v.b))
    return !same_side(u.a, u.b, v) && !same_side(v.a, v.b, u);
  return dot_online_in(u.a, v) || dot_online_in(u.b, v) ||
         dot_online_in(v.a, u) || dot_online_in(v.b, u);
}
int intersect_in(point u1, point u2, point v1, point v2) {
  if (!dots_inline(u1, u2, v1) || !dots_inline(u1, u2, v2))
    return !same_side(u1, u2, v1, v2) && !same_side(v1, v2, u1, u2);
  return dot_online_in(u1, v1, v2) || dot_online_in(u2, v1, v2) ||
         dot_online_in(v1, u1, u2) || dot_online_in(v2, u1, u2);
}
int intersect_ex(line u, line v) {
  return opposite_side(u.a, u.b, v) && opposite_side(v.a, v.b, u);
}
int intersect_ex(point u1, point u2, point v1, point v2) {
  return opposite_side(u1, u2, v1, v2) && opposite_side(v1, v2, u1, u2);
}
point ptoline(point p, line l) {
  point t = p;
  t.x += l.a.y - l.b.y, t.y += l.b.x - l.a.x;
  return intersection(p, t, l.a, l.b);
}
point ptoline(point p, point l1, point l2) {
  point t = p;
  t.x += l1.y - l2.y, t.y += l2.x - l1.x;
  return intersection(p, t, l1, l2);
}
double disptoline(point p, line l) {
  return fabs(xmult(p, l.a, l.b)) / Distance(l.a, l.b);
}
double disptoline(double x, double y, double x1, double y1, double x2,
                  double y2) {
  return fabs(xmult(x, y, x1, y1, x2, y2)) / Distance(x1, y1, x2, y2);
}
point ptoseg(point p, line l) {
  point t = p;
  t.x += l.a.y - l.b.y, t.y += l.b.x - l.a.x;
  if (xmult(l.a, t, p) * xmult(l.b, t, p) > 1e-1)
    return Distance(p, l.a) < Distance(p, l.b) ? l.a : l.b;
  return intersection(p, t, l.a, l.b);
}
point ptoseg(point p, point l1, point l2) {
  point t = p;
  t.x += l1.y - l2.y, t.y += l2.x - l1.x;
  if (xmult(l1, t, p) * xmult(l2, t, p) > 1e-1)
    return Distance(p, l1) < Distance(p, l2) ? l1 : l2;
  return intersection(p, t, l1, l2);
}
double disptoseg(point p, line l) {
  point t = p;
  t.x += l.a.y - l.b.y, t.y += l.b.x - l.a.x;
  if (xmult(l.a, t, p) * xmult(l.b, t, p) > 1e-1)
    return Distance(p, l.a) < Distance(p, l.b) ? Distance(p, l.a)
                                               : Distance(p, l.b);
  return fabs(xmult(p, l.a, l.b)) / Distance(l.a, l.b);
}
double disptoseg(point p, point l1, point l2) {
  point t = p;
  t.x += l1.y - l2.y, t.y += l2.x - l1.x;
  if (xmult(l1, t, p) * xmult(l2, t, p) > 1e-1)
    return Distance(p, l1) < Distance(p, l2) ? Distance(p, l1)
                                             : Distance(p, l2);
  return fabs(xmult(p, l1, l2)) / Distance(l1, l2);
}
point rotate(point v, point p, double angle, double scale) {
  point ret = p;
  v.x -= p.x, v.y -= p.y;
  p.x = scale * cos(angle);
  p.y = scale * sin(angle);
  ret.x += v.x * p.x - v.y * p.y;
  ret.y += v.x * p.y + v.y * p.x;
  return ret;
}
double area_triangle(point p1, point p2, point p3) {
  return fabs(xmult(p1, p2, p3)) / 2;
}
double area_triangle(double x1, double y1, double x2, double y2, double x3,
                     double y3) {
  return fabs(xmult(x1, y1, x2, y2, x3, y3)) / 2;
}
double area_triangle(double a, double b, double c) {
  double s = (a + b + c) / 2;
  return sqrt(s * (s - a) * (s - b) * (s - c));
}
double area_polygon(int n, point* p) {
  double s1 = 0, s2 = 0;
  int i;
  for (i = 0; i < n; i++)
    s1 += p[(i + 1) % n].y * p[i].x, s2 += p[(i + 1) % n].y * p[(i + 2) % n].x;
  return fabs(s1 - s2) / 2;
}
const double pi = acos(-1);
double angle(double lng1, double lat1, double lng2, double lat2) {
  double dlng = fabs(lng1 - lng2) * pi / 180;
  while (dlng >= pi + pi) dlng -= pi + pi;
  if (dlng > pi) dlng = pi + pi - dlng;
  lat1 *= pi / 180, lat2 *= pi / 180;
  return acos(cos(lat1) * cos(lat2) * cos(dlng) + sin(lat1) * sin(lat2));
}
double line_dist(double r, double lng1, double lat1, double lng2, double lat2) {
  double dlng = fabs(lng1 - lng2) * pi / 180;
  while (dlng >= pi + pi) dlng -= pi + pi;
  if (dlng > pi) dlng = pi + pi - dlng;
  lat1 *= pi / 180, lat2 *= pi / 180;
  return r * sqrt(2 - 2 * (cos(lat1) * cos(lat2) * cos(dlng) +
                           sin(lat1) * sin(lat2)));
}
inline double sphere_dist(double r, double lng1, double lat1, double lng2,
                          double lat2) {
  return r * angle(lng1, lat1, lng2, lat2);
}
point circumcenter(point a, point b, point c) {
  line u, v;
  u.a.x = (a.x + b.x) / 2;
  u.a.y = (a.y + b.y) / 2;
  u.b.x = u.a.x - a.y + b.y;
  u.b.y = u.a.y + a.x - b.x;
  v.a.x = (a.x + c.x) / 2;
  v.a.y = (a.y + c.y) / 2;
  v.b.x = v.a.x - a.y + c.y;
  v.b.y = v.a.y + a.x - c.x;
  return intersection(u, v);
}
point incenter(point a, point b, point c) {
  line u, v;
  double m, n;
  u.a = a;
  m = atan2(b.y - a.y, b.x - a.x);
  n = atan2(c.y - a.y, c.x - a.x);
  u.b.x = u.a.x + cos((m + n) / 2);
  u.b.y = u.a.y + sin((m + n) / 2);
  v.a = b;
  m = atan2(a.y - b.y, a.x - b.x);
  n = atan2(c.y - b.y, c.x - b.x);
  v.b.x = v.a.x + cos((m + n) / 2);
  v.b.y = v.a.y + sin((m + n) / 2);
  return intersection(u, v);
}
point perpencenter(point a, point b, point c) {
  line u, v;
  u.a = c;
  u.b.x = u.a.x - a.y + b.y;
  u.b.y = u.a.y + a.x - b.x;
  v.a = b;
  v.b.x = v.a.x - a.y + c.y;
  v.b.y = v.a.y + a.x - c.x;
  return intersection(u, v);
}
point barycenter(point a, point b, point c) {
  line u, v;
  u.a.x = (a.x + b.x) / 2;
  u.a.y = (a.y + b.y) / 2;
  u.b = c;
  v.a.x = (a.x + c.x) / 2;
  v.a.y = (a.y + c.y) / 2;
  v.b = b;
  return intersection(u, v);
}
point fermentpoint(point a, point b, point c) {
  point u, v;
  double step =
      fabs(a.x) + fabs(a.y) + fabs(b.x) + fabs(b.y) + fabs(c.x) + fabs(c.y);
  int i, j, k;
  u.x = (a.x + b.x + c.x) / 3;
  u.y = (a.y + b.y + c.y) / 3;
  while (step > 1e-10)
    for (k = 0; k < 10; step /= 2, k++)
      for (i = -1; i <= 1; i++)
        for (j = -1; j <= 1; j++) {
          v.x = u.x + step * i;
          v.y = u.y + step * j;
          if (Distance(u, a) + Distance(u, b) + Distance(u, c) >
              Distance(v, a) + Distance(v, b) + Distance(v, c))
            u = v;
        }
  return u;
}
point p[401];
bool can[400][400];
long long f[400][400];
int n;
const long long mod = 1000000007;
inline bool between(point a, point b, point c) {
  double aa = atan2(a.y, a.x);
  double ab = atan2(b.y, b.x);
  double ac = atan2(c.y, c.x);
  while (ab < aa) ab += 2 * 3.14159265358;
  while (ac < aa) ac += 2 * 3.14159265358;
  return ac < ab;
}
bool inside_polygon(int j1, int j2, int n, point p[], double area) {
  double sq = 0;
  for (int i = 0; i < j1; i++) sq += p[i] * p[i + 1];
  sq += p[j1] * p[j2];
  for (int i = j2; i < n; i++) sq += p[i] * p[i + 1];
  return 0 <= sq && sq <= area;
}
int main() {
  scanf("%d", &n);
  memset(can, true, sizeof(can));
  for (int i = 0; i < n; i++) {
    scanf("%lf %lf", &p[i].x, &p[i].y);
  }
  p[n] = p[0];
  double sq = 0;
  for (int i = 0; i < n; i++) sq += p[i] * p[i + 1];
  if (sq < 0) {
    reverse(p, p + n);
    p[n] = p[0];
    sq = -sq;
  }
  for (int i = 0; i < n; i++)
    for (int j = i + 2; j < n; j++) {
      if (i == 0 && j == n - 1) continue;
      if (!inside_polygon(i, j, n, p, sq)) {
        can[i][j] = can[j][i] = false;
        continue;
      }
      for (int k = 0; k < n; k++)
        if (intersect_ex(p[i], p[j], p[k], p[k + 1]) ||
            dot_online_ex(p[k], p[i], p[j])) {
          can[i][j] = can[j][i] = false;
          break;
        }
    }
  memset(f, 0, sizeof(f));
  for (int i = 0; i < n; i++) {
    if (can[i][(i + 2 >= n ? i + 2 - n : i + 2)])
      f[i][(i + 2 >= n ? i + 2 - n : i + 2)] = 1;
    f[i][(i + 1 >= n ? i + 1 - n : i + 1)] = 1;
  }
  for (int d = 3; d <= n - 1; d++) {
    for (int i = 0; i < n; i++) {
      int id = (i + d >= n ? i + d - n : i + d);
      if (can[i][id])
        for (int j = i + 1; j <= d + i - 1; j++)
          if (can[i][(j >= n ? j - n : j)] && can[(j >= n ? j - n : j)][id]) {
            f[i][id] = (f[i][id] + f[i][(j >= n ? j - n : j)] *
                                       f[(j >= n ? j - n : j)][id]) %
                       mod;
          }
    }
  }
  cout << f[0][n - 1] << endl;
}
