Problem: Gerald got tired of playing board games with the usual six-sided die, and he bought a toy called Randomizer. It functions as follows.

A Randomizer has its own coordinate plane on which a strictly convex polygon is painted, the polygon is called a basic polygon. If you shake a Randomizer, it draws some nondegenerate (i.e. having a non-zero area) convex polygon with vertices at some vertices of the basic polygon. The result of the roll (more precisely, the result of the shaking) is considered to be the number of points with integer coordinates, which were strictly inside (the points on the border are not considered) the selected polygon. Now Gerald is wondering: what is the expected result of shaking the Randomizer?

During the shaking the Randomizer considers all the possible non-degenerate convex polygons with vertices at the vertices of the basic polygon. Let's assume that there are k versions of the polygons. Then the Randomizer chooses each of them with probability <image>.

Input

The first line of the input contains a single integer n (3 ≤ n ≤ 100 000) — the number of vertices of the basic polygon. 

Next n lines contain the coordinates of the vertices of the basic polygon. The i-th of these lines contain two integers xi and yi ( - 109 ≤ xi, yi ≤ 109) — the coordinates of the i-th vertex of the polygon. The vertices are given in the counter-clockwise order.

Output

Print the sought expected value with absolute or relative error at most 10 - 9.

Examples

Input

4
0 0
2 0
2 2
0 2


Output

0.2


Input

5
0 0
2 0
2 2
1 3
0 2


Output

0.8125

Note

A polygon is called strictly convex if it is convex and no its vertices lie on the same line.

Let's assume that a random variable takes values x1, ..., xn with probabilities p1, ..., pn, correspondingly. Then the expected value of this variable equals to <image>.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vb = vector<bool>;
using vd = vector<double>;
using vs = vector<string>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<double, double>;
using vpii = vector<pii>;
using vvpii = vector<vpii>;
using vpll = vector<pll>;
using vvpll = vector<vpll>;
using vpdd = vector<pdd>;
using vvpdd = vector<vpdd>;
template <typename T>
void ckmin(T& a, const T& b) {
  a = min(a, b);
}
template <typename T>
void ckmax(T& a, const T& b) {
  a = max(a, b);
}
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
namespace __input {
template <class T1, class T2>
void re(pair<T1, T2>& p);
template <class T>
void re(vector<T>& a);
template <class T, size_t SZ>
void re(array<T, SZ>& a);
template <class T>
void re(T& x) {
  cin >> x;
}
void re(double& x) {
  string t;
  re(t);
  x = stod(t);
}
template <class Arg, class... Args>
void re(Arg& first, Args&... rest) {
  re(first);
  re(rest...);
}
template <class T1, class T2>
void re(pair<T1, T2>& p) {
  re(p.first, p.second);
}
template <class T>
void re(vector<T>& a) {
  for (int i = 0; i < (int((a).size())); i++) re(a[i]);
}
template <class T, size_t SZ>
void re(array<T, SZ>& a) {
  for (int i = 0; i < (SZ); i++) re(a[i]);
}
}  // namespace __input
using namespace __input;
namespace __output {
template <class T1, class T2>
void pr(const pair<T1, T2>& x);
template <class T, size_t SZ>
void pr(const array<T, SZ>& x);
template <class T>
void pr(const vector<T>& x);
template <class T>
void pr(const deque<T>& x);
template <class T>
void pr(const set<T>& x);
template <class T1, class T2>
void pr(const map<T1, T2>& x);
template <class T>
void pr(const T& x) {
  cout << x;
}
template <class Arg, class... Args>
void pr(const Arg& first, const Args&... rest) {
  pr(first);
  pr(rest...);
}
template <class T1, class T2>
void pr(const pair<T1, T2>& x) {
  pr("{", x.first, ", ", x.second, "}");
}
template <class T, bool pretty = true>
void prContain(const T& x) {
  if (pretty) pr("{");
  bool fst = 1;
  for (const auto& a : x) pr(!fst ? pretty ? ", " : " " : "", a), fst = 0;
  if (pretty) pr("}");
}
template <class T>
void pc(const T& x) {
  prContain<T, false>(x);
  pr("\n");
}
template <class T, size_t SZ>
void pr(const array<T, SZ>& x) {
  prContain(x);
}
template <class T>
void pr(const vector<T>& x) {
  prContain(x);
}
template <class T>
void pr(const deque<T>& x) {
  prContain(x);
}
template <class T>
void pr(const set<T>& x) {
  prContain(x);
}
template <class T1, class T2>
void pr(const map<T1, T2>& x) {
  prContain(x);
}
void ps() { pr("\n"); }
template <class Arg>
void ps(const Arg& first) {
  pr(first);
  ps();
}
template <class Arg, class... Args>
void ps(const Arg& first, const Args&... rest) {
  pr(first, " ");
  ps(rest...);
}
}  // namespace __output
using namespace __output;
namespace __algorithm {
template <typename T>
void dedup(vector<T>& v) {
  sort((v).begin(), (v).end());
  v.erase(unique((v).begin(), (v).end()), v.end());
}
template <typename T>
typename vector<T>::iterator find(vector<T>& v, const T& x) {
  auto it = lower_bound((v).begin(), (v).end(), x);
  return it != v.end() && *it == x ? it : v.end();
}
template <typename T>
size_t index(vector<T>& v, const T& x) {
  auto it = find(v, x);
  assert(it != v.end() && *it == x);
  return it - v.begin();
}
template <typename C, typename T, typename OP>
vector<T> prefixes(const C& v, T id, OP op) {
  vector<T> r(int((v).size()) + 1, id);
  for (int i = 0; i < (int((v).size())); i++) r[i + 1] = op(r[i], v[i]);
  return r;
}
template <typename C, typename T, typename OP>
vector<T> suffixes(const C& v, T id, OP op) {
  vector<T> r(int((v).size()) + 1, id);
  for (int i = (int((v).size())) - 1; i >= 0; i--) r[i] = op(v[i], r[i + 1]);
  return r;
}
}  // namespace __algorithm
using namespace __algorithm;
struct monostate {
  friend istream& operator>>(istream& is,
                             const __attribute__((unused)) monostate& ms) {
    return is;
  }
  friend ostream& operator<<(ostream& os,
                             const __attribute__((unused)) monostate& ms) {
    return os;
  }
} ms;
template <typename W = monostate>
struct wedge {
  int u, v, i;
  W w;
  wedge<W>(int _u = -1, int _v = -1, int _i = -1) : u(_u), v(_v), i(_i) {}
  int operator[](int loc) const { return u ^ v ^ loc; }
  friend void re(wedge& e) {
    re(e.u, e.v, e.w);
    --e.u, --e.v;
  }
  friend void pr(const wedge& e) { pr(e.u, "<-", e.w, "->", e.v); }
};
namespace __io {
void setIn(string second) { freopen(second.c_str(), "r", stdin); }
void setOut(string second) { freopen(second.c_str(), "w", stdout); }
void setIO(string second = "") {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout << fixed << setprecision(15);
  if (int((second).size())) {
    setIn(second + ".in"), setOut(second + ".out");
  }
}
}  // namespace __io
using namespace __io;
template <typename T>
struct point {
  T x, y;
  point() : x(0), y(0) {}
  point(T _x, T _y) : x(_x), y(_y) {}
  friend istream& operator>>(istream& i, point& p) { return i >> p.x >> p.y; }
  friend ostream& operator<<(ostream& o, const point& p) {
    return o << "(" << p.x << ", " << p.y << ")";
  }
  T norm() const { return x * x + y * y; }
  double len() const { return sqrt(norm()); }
  double ang() const { return atan2(y, x); }
  point<T> conj() const { return {x, -y}; }
  point& operator+=(const point& o) {
    x += o.x;
    y += o.y;
    return *this;
  }
  point& operator-=(const point& o) {
    x -= o.x;
    y -= o.y;
    return *this;
  }
  point& operator*=(const T& c) {
    x *= c;
    y *= c;
    return *this;
  }
  point& operator/=(const T& c) {
    x /= c;
    y /= c;
    return *this;
  }
  friend point operator+(const point& a, const point& b) {
    return point(a) += b;
  }
  friend point operator-(const point& a, const point& b) {
    return point(a) -= b;
  }
  friend point operator*(const point& a, const T& c) { return point(a) *= c; }
  friend point operator*(const T& c, const point& a) { return point(a) *= c; }
  friend point operator/(const point& a, const T& c) { return point(a) /= c; }
  bool operator==(const point& o) const { return x == o.x && y == o.y; }
  bool operator!=(const point& o) const { return x != o.x || y != o.y; }
  bool operator<(const point& o) const {
    return (x != o.x) ? x < o.x : y < o.y;
  }
  bool operator>(const point& o) const {
    return (x != o.x) ? x > o.x : y > o.y;
  }
  bool operator<=(const point& o) const { return !(*this > o); }
  friend T dot(const point& a, const point& b) { return a.x * b.x + a.y * b.y; }
  friend T cross(const point& a, const point& b) {
    return a.x * b.y - a.y * b.x;
  }
  friend T cross(const point& p, const point& a, const point& b) {
    return cross(a - p, b - p);
  }
  friend point<T> operator*(const point& a, const point& b) {
    return {a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x};
  }
  friend point<T> operator/(const point& a, const point& b) {
    return a * b.conj() / b.norm();
  }
  point dir() const { return point(*this) / len(); }
  point rotate(const double& ang) const {
    return *this * point(cos(ang), sin(ang));
  }
  T dist(const point& a) const { return (a - *this).len(); }
  T dist(const point& a, const point& b) {
    return abs(cross(*this, a, b)) / a.dist(b);
  }
  point reflect(const point& a, const point& b) const {
    return a + ((*this - a) / (b - a)).conj() * (b - a);
  }
  point foot(const point& a, const point& b) const {
    return (*this + this->reflect(a, b)) / 2;
  }
  friend point extension(const point& a, const point& b, const point& c,
                         const point& d) {
    T x = cross(a, b, c), y = cross(a, b, d);
    return (d * x - c * y) / (x - y);
  }
  friend vector<point> seg_intersect(point a, point b, point c, point d) {
    if (a > b) swap(a, b);
    if (c > d) swap(c, d);
    T a1 = cross(a, b, c), a2 = cross(a, b, d);
    if (a1 > a2) swap(a1, a2);
    if (!(a1 <= 0 && a2 >= 0)) return {};
    if (a1 == 0 && a2 == 0) {
      if (cross(a, c, d) != 0) return {};
      point<T> x1 = max(a, c), x2 = min(b, d);
      if (x1 > x2) return {};
      if (x1 == x2) return {x1};
      return {x1, x2};
    }
    point<T> z = extension(a, b, c, d);
    if (a <= z && z <= b) return {z};
    return {};
  }
  using polygon = vector<point<T>>;
  friend ostream& operator<<(ostream& o, const polygon& poly) {
    o << "{";
    for (auto pt : poly) o << " " << pt;
    return o << " }";
  }
  string classify(const polygon& p) const {
    bool ans = 0;
    for (int i = 0; i < p.size(); i++) {
      point<T> a = p[i], b = p[(i + 1) % p.size()];
      if (cross(a, b, *this) == 0 && min(a, b) <= *this && *this <= max(a, b))
        return "on";
      if (a.y > b.y) swap(a, b);
      if (a.y <= y && y < b.y && cross(*this, a, b) > 0) ans ^= 1;
    }
    return ans ? "in" : "out";
  }
  friend polygon convex_hull(const vector<point>& pts) {
    point pivot = *min_element((pts).begin(), (pts).end());
    auto sorted = pts;
    sort((sorted).begin(), (sorted).end(),
         [&pivot](const point& p, const point& q) {
           T cp = cross(pivot, p, q);
           if (cp != 0) return cp > 0;
           return pivot.dist(p) < pivot.dist(q);
         });
    int j = 0;
    polygon res(pts.size());
    for (const point& p : sorted) {
      while (j > 1 && cross(res[j - 2], res[j - 1], p) <= 0) j--;
      res[j++] = p;
    }
    res.erase(res.begin() + j, res.end());
    return res;
  }
  friend T area(const polygon& p) {
    T a = 0;
    for (int i = 0; i < int((p).size()); i++)
      a += cross(p[i], p[i + 1 < int((p).size()) ? i + 1 : 0]);
    return a;
  }
  static T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
  friend T lattice(const point& a, const point& b) {
    if (a == b) return 0;
    return gcd(abs(a.x - b.x), abs(a.y - b.y)) - 1;
  }
  friend T lattice(const polygon& p) {
    T r = abs(area(p)) + 2;
    for (int i = 0; i < int((p).size()); i++) {
      r -= 1 + lattice(p[i], p[i + 1 < int((p).size()) ? i + 1 : 0]);
    }
    assert(r % 2 == 0);
    return r / 2;
  }
};
int main() {
  setIO();
  using pt = point<ll>;
  int N;
  re(N);
  vector<pt> p(N);
  for (int i = 0; i < (N); i++) {
    int x, y;
    re(x, y);
    p[i] = {x, y};
  }
  double ans = lattice(p);
  for (int i = 0; i < (N); i++) p.push_back(p[i]);
  const int B = 100;
  vd p2(B);
  p2[0] = 1;
  for (int i = (1); i < (B); i++) p2[i] = p2[i - 1] / 2;
  double de = 1;
  if (N < B) de -= (1 + N + double(N) * (N - 1) / 2) * p2[N];
  vll cr(int((p).size()));
  for (int i = 0; i < (int((p).size()) - 1); i++) cr[i] = cross(p[i], p[i + 1]);
  vi lat(int((p).size()));
  for (int i = 0; i < (int((p).size()) - 1); i++)
    lat[i] = lattice(p[i], p[i + 1]);
  for (int i = 0; i < (N); i++) {
    ll a = 0, b = 2 * (1 + lattice(p[i], p[i + 1]));
    ll _a = cross(p[i + 1], p[i]), _b = lattice(p[i + 1], p[i]) + 1;
    for (int k = (2); k < (min(N, 60)); k++) {
      a -= _a;
      a += cr[i + k - 1];
      a += (_a = cross(p[i + k], p[i]));
      b -= _b;
      b += lat[i + k - 1] + 1;
      b += (_b = lattice(p[i + k], p[i]) + 1);
      double nu = p2[k + 1];
      if (N < B) nu -= p2[N];
      ans -= nu / de * (_b - 1 + (abs(a) + 2 - b) / 2);
    }
  }
  ps(ans);
  return 0;
}