#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
const int& MOD = mod;
const long long INF = 2e18 + 10;
template <typename T1, typename T2>
bool sort_by_sec(pair<T1, T2> a, pair<T1, T2> b) {
  return make_pair(a.second, a.first) < make_pair(b.second, b.first);
}
long long multiply(long long a, long long b, long long in_mod) {
  return (long long)(1LL * a * b % in_mod);
}
long long mult_identity(long long a) { return 1; }
vector<long long> multiply(const vector<long long>& a,
                           const vector<long long>& b, long long mod);
vector<long long> mult_identity(vector<long long> a) { return {1}; }
const double PI = acosl(-1);
long long power(long long a, long long b, long long in_mod) {
  long long prod = 1;
  long long mult = a % in_mod;
  while (b != 0) {
    if (b % 2) {
      prod = multiply(prod, mult, in_mod);
    }
    mult = multiply(mult, mult, in_mod);
    b /= 2;
  }
  return prod;
}
long long mod_inv(long long q, long long in_mod) {
  return power(q, in_mod - 2, in_mod);
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T>
T inverse(T a, T m) {
  T u = 0, v = 1;
  while (a != 0) {
    T t = m / a;
    m -= t * a;
    swap(a, m);
    u -= t * v;
    swap(u, v);
  }
  assert(m == 1);
  return u;
}
template <typename T>
class Modular {
 public:
  using Type = typename decay<decltype(T::value)>::type;
  constexpr Modular() : value() {}
  template <typename U>
  Modular(const U& x) {
    value = normalize(x);
  }
  template <typename U>
  static Type normalize(const U& x) {
    Type v;
    if (-mod() <= x && x < mod())
      v = static_cast<Type>(x);
    else
      v = static_cast<Type>(x % mod());
    if (v < 0) v += mod();
    return v;
  }
  const Type& operator()() const { return value; }
  template <typename U>
  explicit operator U() const {
    return static_cast<U>(value);
  }
  constexpr static Type mod() { return T::value; }
  Modular& operator+=(const Modular& other) {
    if ((value += other.value) >= mod()) value -= mod();
    return *this;
  }
  Modular& operator-=(const Modular& other) {
    if ((value -= other.value) < 0) value += mod();
    return *this;
  }
  template <typename U>
  Modular& operator+=(const U& other) {
    return *this += Modular(other);
  }
  template <typename U>
  Modular& operator-=(const U& other) {
    return *this -= Modular(other);
  }
  Modular& operator++() { return *this += 1; }
  Modular& operator--() { return *this -= 1; }
  Modular operator++(signed) {
    Modular result(*this);
    *this += 1;
    return result;
  }
  Modular operator--(signed) {
    Modular result(*this);
    *this -= 1;
    return result;
  }
  Modular operator-() const { return Modular(-value); }
  template <typename U = T>
  typename enable_if<is_same<typename Modular<U>::Type, int>::value,
                     Modular>::type&
  operator*=(const Modular& rhs) {
    value = normalize(static_cast<int64_t>(value) *
                      static_cast<int64_t>(rhs.value));
    return *this;
  }
  template <typename U = T>
  typename enable_if<is_same<typename Modular<U>::Type, int64_t>::value,
                     Modular>::type&
  operator*=(const Modular& rhs) {
    int64_t q = static_cast<int64_t>(static_cast<long double>(value) *
                                     rhs.value / mod());
    value = normalize(value * rhs.value - q * mod());
    return *this;
  }
  template <typename U = T>
  typename enable_if<!is_integral<typename Modular<U>::Type>::value,
                     Modular>::type&
  operator*=(const Modular& rhs) {
    value = normalize(value * rhs.value);
    return *this;
  }
  Modular& operator/=(const Modular& other) {
    return *this *= Modular(inverse(other.value, mod()));
  }
  template <typename U>
  friend const Modular<U>& abs(const Modular<U>& v) {
    return v;
  }
  template <typename U>
  friend bool operator==(const Modular<U>& lhs, const Modular<U>& rhs);
  template <typename U>
  friend bool operator<(const Modular<U>& lhs, const Modular<U>& rhs);
  template <typename U>
  friend std::istream& operator>>(std::istream& stream, Modular<U>& number);

 private:
  Type value;
};
template <typename T>
bool operator==(const Modular<T>& lhs, const Modular<T>& rhs) {
  return lhs.value == rhs.value;
}
template <typename T, typename U>
bool operator==(const Modular<T>& lhs, U rhs) {
  return lhs == Modular<T>(rhs);
}
template <typename T, typename U>
bool operator==(U lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) == rhs;
}
template <typename T>
bool operator!=(const Modular<T>& lhs, const Modular<T>& rhs) {
  return !(lhs == rhs);
}
template <typename T, typename U>
bool operator!=(const Modular<T>& lhs, U rhs) {
  return !(lhs == rhs);
}
template <typename T, typename U>
bool operator!=(U lhs, const Modular<T>& rhs) {
  return !(lhs == rhs);
}
template <typename T>
bool operator<(const Modular<T>& lhs, const Modular<T>& rhs) {
  return lhs.value < rhs.value;
}
template <typename T>
Modular<T> operator+(const Modular<T>& lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) += rhs;
}
template <typename T, typename U>
Modular<T> operator+(const Modular<T>& lhs, U rhs) {
  return Modular<T>(lhs) += rhs;
}
template <typename T, typename U>
Modular<T> operator+(U lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) += rhs;
}
template <typename T>
Modular<T> operator-(const Modular<T>& lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) -= rhs;
}
template <typename T, typename U>
Modular<T> operator-(const Modular<T>& lhs, U rhs) {
  return Modular<T>(lhs) -= rhs;
}
template <typename T, typename U>
Modular<T> operator-(U lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) -= rhs;
}
template <typename T>
Modular<T> operator*(const Modular<T>& lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) *= rhs;
}
template <typename T, typename U>
Modular<T> operator*(const Modular<T>& lhs, U rhs) {
  return Modular<T>(lhs) *= rhs;
}
template <typename T, typename U>
Modular<T> operator*(U lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) *= rhs;
}
template <typename T>
Modular<T> operator/(const Modular<T>& lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) /= rhs;
}
template <typename T, typename U>
Modular<T> operator/(const Modular<T>& lhs, U rhs) {
  return Modular<T>(lhs) /= rhs;
}
template <typename T, typename U>
Modular<T> operator/(U lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) /= rhs;
}
template <typename T, typename U>
Modular<T> power(const Modular<T>& a, const U& b) {
  assert(b >= 0);
  Modular<T> x = a, res = 1;
  U p = b;
  while (p > 0) {
    if (p & 1) res *= x;
    x *= x;
    p >>= 1;
  }
  return res;
}
template <typename T>
bool IsZero(const Modular<T>& number) {
  return number() == 0;
}
template <typename T>
string to_string(const Modular<T>& number) {
  return to_string(number());
}
template <typename T>
std::ostream& operator<<(std::ostream& stream, const Modular<T>& number) {
  return stream << number();
}
template <typename T>
std::istream& operator>>(std::istream& stream, Modular<T>& number) {
  typename common_type<typename Modular<T>::Type, int64_t>::type x;
  stream >> x;
  number.value = Modular<T>::normalize(x);
  return stream;
}
constexpr int md = 2;
using Mint = Modular<std::integral_constant<decay<decltype(md)>::type, md>>;
Mint pwr(Mint a, int k) {
  Mint ans = 1;
  while (k) {
    if (k & 1) ans = ans * a;
    a = a * a;
    k >>= 1;
  }
  return ans;
}
int sm;
vector<int> where;
const int maxn = 5e5 + 100;
int gauss(vector<bitset<maxn>>& a) {
  int n = (int)a.size();
  int m = (int)a[0].size() - 1;
  vector<int> where(m, -1);
  for (int col = 0, row = 0; col < m && row < n; ++col) {
    for (int i = row; i < n; ++i)
      if (a[i][col]) {
        swap(a[i], a[row]);
        break;
      }
    if (!a[row][col]) continue;
    where[col] = row;
    for (int i = 0; i < n; ++i)
      if (i != row && a[i][col]) a[i] ^= a[row];
    ++row;
  }
  int sm = 0;
  for (int i = 0; i < m; ++i)
    if (where[i] == -1) sm++;
  ::sm = sm;
  ::where = where;
  vector<Mint> ans(m);
  ans.assign(m, 0);
  for (int i = 0; i < m; ++i)
    if (where[i] != -1) ans[i] = a[where[i]][m] / a[where[i]][i];
  for (int i = 0; i < n; ++i) {
    Mint sum = 0;
    for (int j = 0; j < m; ++j) sum += ans[j] * (signed)a[i][j];
    if (abs(sum - a[i][m]) != 0) {
      cout << 1 << "/" << 1 << endl;
      return 0;
    }
  }
  if (sm) {
    cout << power((long long)2, (long long)m - sm, (long long)INF) - 1 << "/"
         << power((long long)2, (long long)m - sm, (long long)INF) << endl;
    return power(2, sm, mod);
  }
  cout << "0/1" << endl;
  return 1;
}
void solve() {
  int n;
  cin >> n;
  vector<bitset<maxn>> mat(63);
  ;
  long long x = 0;
  for (int i = 0; i < n; i++) {
    long long a, b;
    cin >> a >> b;
    x ^= (a);
    long long t = a ^ b;
    for (int j = 0; j < 63; j++) {
      if (t & ((long long)1 << j)) {
        mat[j][i] = 1;
      }
    }
  }
  for (int j = 0; j < 63; j++) {
    if (x & ((long long)1 << j)) mat[j][maxn - 1] = 1;
  }
  gauss(mat);
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cerr.tie(NULL);
  auto clk = clock();
  int t = 1;
  for (int test = 1; test <= t; test++) {
    solve();
  }
  clk = clock() - clk;
  cerr << fixed << setprecision(6)
       << "\nTime: " << ((double)clk) / CLOCKS_PER_SEC << "\n";
  return 0;
}

### Prompt

Create a solution in Cpp for the following problem:

As you know, the game of "Nim" is played with n piles of stones, where the i-th pile initially contains ai stones. Two players alternate the turns. During a turn a player picks any non-empty pile and removes any positive number of stones from it. The one who is not able to make a move loses the game.

Petya and Vasya are tired of playing Nim, so they invented their own version of the game and named it the "Gambling Nim". They have n two-sided cards, one side of the i-th card has number ai written on it, while the other side has number bi. At the beginning of the game the players put all the cards on the table, each card only one of its sides up, and this side is chosen independently and uniformly. Thus they obtain a sequence c1, c2, ..., cn, where ci is equal to ai or bi. Then they take n piles of stones, with i-th pile containing exactly ci stones and play Nim. Petya takes the first turn.

Given that both players play optimally, find the probability of Petya's victory. Output the answer as an irreducible fraction.

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 500 000) — the number of cards in the deck.

Each of the following n lines contains the description of one card, consisting of two integers ai and bi (0 ≤ ai, bi ≤ 1018).

Output

Output the answer as an irreducible fraction p / q. If the probability of Petya's victory is 0, print 0/1.

Examples

Input

2
1 1
1 1


Output

0/1


Input

2
1 2
1 2


Output

1/2


Input

3
0 4
1 5
2 3


Output

1/1

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
const int& MOD = mod;
const long long INF = 2e18 + 10;
template <typename T1, typename T2>
bool sort_by_sec(pair<T1, T2> a, pair<T1, T2> b) {
  return make_pair(a.second, a.first) < make_pair(b.second, b.first);
}
long long multiply(long long a, long long b, long long in_mod) {
  return (long long)(1LL * a * b % in_mod);
}
long long mult_identity(long long a) { return 1; }
vector<long long> multiply(const vector<long long>& a,
                           const vector<long long>& b, long long mod);
vector<long long> mult_identity(vector<long long> a) { return {1}; }
const double PI = acosl(-1);
long long power(long long a, long long b, long long in_mod) {
  long long prod = 1;
  long long mult = a % in_mod;
  while (b != 0) {
    if (b % 2) {
      prod = multiply(prod, mult, in_mod);
    }
    mult = multiply(mult, mult, in_mod);
    b /= 2;
  }
  return prod;
}
long long mod_inv(long long q, long long in_mod) {
  return power(q, in_mod - 2, in_mod);
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T>
T inverse(T a, T m) {
  T u = 0, v = 1;
  while (a != 0) {
    T t = m / a;
    m -= t * a;
    swap(a, m);
    u -= t * v;
    swap(u, v);
  }
  assert(m == 1);
  return u;
}
template <typename T>
class Modular {
 public:
  using Type = typename decay<decltype(T::value)>::type;
  constexpr Modular() : value() {}
  template <typename U>
  Modular(const U& x) {
    value = normalize(x);
  }
  template <typename U>
  static Type normalize(const U& x) {
    Type v;
    if (-mod() <= x && x < mod())
      v = static_cast<Type>(x);
    else
      v = static_cast<Type>(x % mod());
    if (v < 0) v += mod();
    return v;
  }
  const Type& operator()() const { return value; }
  template <typename U>
  explicit operator U() const {
    return static_cast<U>(value);
  }
  constexpr static Type mod() { return T::value; }
  Modular& operator+=(const Modular& other) {
    if ((value += other.value) >= mod()) value -= mod();
    return *this;
  }
  Modular& operator-=(const Modular& other) {
    if ((value -= other.value) < 0) value += mod();
    return *this;
  }
  template <typename U>
  Modular& operator+=(const U& other) {
    return *this += Modular(other);
  }
  template <typename U>
  Modular& operator-=(const U& other) {
    return *this -= Modular(other);
  }
  Modular& operator++() { return *this += 1; }
  Modular& operator--() { return *this -= 1; }
  Modular operator++(signed) {
    Modular result(*this);
    *this += 1;
    return result;
  }
  Modular operator--(signed) {
    Modular result(*this);
    *this -= 1;
    return result;
  }
  Modular operator-() const { return Modular(-value); }
  template <typename U = T>
  typename enable_if<is_same<typename Modular<U>::Type, int>::value,
                     Modular>::type&
  operator*=(const Modular& rhs) {
    value = normalize(static_cast<int64_t>(value) *
                      static_cast<int64_t>(rhs.value));
    return *this;
  }
  template <typename U = T>
  typename enable_if<is_same<typename Modular<U>::Type, int64_t>::value,
                     Modular>::type&
  operator*=(const Modular& rhs) {
    int64_t q = static_cast<int64_t>(static_cast<long double>(value) *
                                     rhs.value / mod());
    value = normalize(value * rhs.value - q * mod());
    return *this;
  }
  template <typename U = T>
  typename enable_if<!is_integral<typename Modular<U>::Type>::value,
                     Modular>::type&
  operator*=(const Modular& rhs) {
    value = normalize(value * rhs.value);
    return *this;
  }
  Modular& operator/=(const Modular& other) {
    return *this *= Modular(inverse(other.value, mod()));
  }
  template <typename U>
  friend const Modular<U>& abs(const Modular<U>& v) {
    return v;
  }
  template <typename U>
  friend bool operator==(const Modular<U>& lhs, const Modular<U>& rhs);
  template <typename U>
  friend bool operator<(const Modular<U>& lhs, const Modular<U>& rhs);
  template <typename U>
  friend std::istream& operator>>(std::istream& stream, Modular<U>& number);

 private:
  Type value;
};
template <typename T>
bool operator==(const Modular<T>& lhs, const Modular<T>& rhs) {
  return lhs.value == rhs.value;
}
template <typename T, typename U>
bool operator==(const Modular<T>& lhs, U rhs) {
  return lhs == Modular<T>(rhs);
}
template <typename T, typename U>
bool operator==(U lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) == rhs;
}
template <typename T>
bool operator!=(const Modular<T>& lhs, const Modular<T>& rhs) {
  return !(lhs == rhs);
}
template <typename T, typename U>
bool operator!=(const Modular<T>& lhs, U rhs) {
  return !(lhs == rhs);
}
template <typename T, typename U>
bool operator!=(U lhs, const Modular<T>& rhs) {
  return !(lhs == rhs);
}
template <typename T>
bool operator<(const Modular<T>& lhs, const Modular<T>& rhs) {
  return lhs.value < rhs.value;
}
template <typename T>
Modular<T> operator+(const Modular<T>& lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) += rhs;
}
template <typename T, typename U>
Modular<T> operator+(const Modular<T>& lhs, U rhs) {
  return Modular<T>(lhs) += rhs;
}
template <typename T, typename U>
Modular<T> operator+(U lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) += rhs;
}
template <typename T>
Modular<T> operator-(const Modular<T>& lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) -= rhs;
}
template <typename T, typename U>
Modular<T> operator-(const Modular<T>& lhs, U rhs) {
  return Modular<T>(lhs) -= rhs;
}
template <typename T, typename U>
Modular<T> operator-(U lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) -= rhs;
}
template <typename T>
Modular<T> operator*(const Modular<T>& lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) *= rhs;
}
template <typename T, typename U>
Modular<T> operator*(const Modular<T>& lhs, U rhs) {
  return Modular<T>(lhs) *= rhs;
}
template <typename T, typename U>
Modular<T> operator*(U lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) *= rhs;
}
template <typename T>
Modular<T> operator/(const Modular<T>& lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) /= rhs;
}
template <typename T, typename U>
Modular<T> operator/(const Modular<T>& lhs, U rhs) {
  return Modular<T>(lhs) /= rhs;
}
template <typename T, typename U>
Modular<T> operator/(U lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) /= rhs;
}
template <typename T, typename U>
Modular<T> power(const Modular<T>& a, const U& b) {
  assert(b >= 0);
  Modular<T> x = a, res = 1;
  U p = b;
  while (p > 0) {
    if (p & 1) res *= x;
    x *= x;
    p >>= 1;
  }
  return res;
}
template <typename T>
bool IsZero(const Modular<T>& number) {
  return number() == 0;
}
template <typename T>
string to_string(const Modular<T>& number) {
  return to_string(number());
}
template <typename T>
std::ostream& operator<<(std::ostream& stream, const Modular<T>& number) {
  return stream << number();
}
template <typename T>
std::istream& operator>>(std::istream& stream, Modular<T>& number) {
  typename common_type<typename Modular<T>::Type, int64_t>::type x;
  stream >> x;
  number.value = Modular<T>::normalize(x);
  return stream;
}
constexpr int md = 2;
using Mint = Modular<std::integral_constant<decay<decltype(md)>::type, md>>;
Mint pwr(Mint a, int k) {
  Mint ans = 1;
  while (k) {
    if (k & 1) ans = ans * a;
    a = a * a;
    k >>= 1;
  }
  return ans;
}
int sm;
vector<int> where;
const int maxn = 5e5 + 100;
int gauss(vector<bitset<maxn>>& a) {
  int n = (int)a.size();
  int m = (int)a[0].size() - 1;
  vector<int> where(m, -1);
  for (int col = 0, row = 0; col < m && row < n; ++col) {
    for (int i = row; i < n; ++i)
      if (a[i][col]) {
        swap(a[i], a[row]);
        break;
      }
    if (!a[row][col]) continue;
    where[col] = row;
    for (int i = 0; i < n; ++i)
      if (i != row && a[i][col]) a[i] ^= a[row];
    ++row;
  }
  int sm = 0;
  for (int i = 0; i < m; ++i)
    if (where[i] == -1) sm++;
  ::sm = sm;
  ::where = where;
  vector<Mint> ans(m);
  ans.assign(m, 0);
  for (int i = 0; i < m; ++i)
    if (where[i] != -1) ans[i] = a[where[i]][m] / a[where[i]][i];
  for (int i = 0; i < n; ++i) {
    Mint sum = 0;
    for (int j = 0; j < m; ++j) sum += ans[j] * (signed)a[i][j];
    if (abs(sum - a[i][m]) != 0) {
      cout << 1 << "/" << 1 << endl;
      return 0;
    }
  }
  if (sm) {
    cout << power((long long)2, (long long)m - sm, (long long)INF) - 1 << "/"
         << power((long long)2, (long long)m - sm, (long long)INF) << endl;
    return power(2, sm, mod);
  }
  cout << "0/1" << endl;
  return 1;
}
void solve() {
  int n;
  cin >> n;
  vector<bitset<maxn>> mat(63);
  ;
  long long x = 0;
  for (int i = 0; i < n; i++) {
    long long a, b;
    cin >> a >> b;
    x ^= (a);
    long long t = a ^ b;
    for (int j = 0; j < 63; j++) {
      if (t & ((long long)1 << j)) {
        mat[j][i] = 1;
      }
    }
  }
  for (int j = 0; j < 63; j++) {
    if (x & ((long long)1 << j)) mat[j][maxn - 1] = 1;
  }
  gauss(mat);
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cerr.tie(NULL);
  auto clk = clock();
  int t = 1;
  for (int test = 1; test <= t; test++) {
    solve();
  }
  clk = clock() - clk;
  cerr << fixed << setprecision(6)
       << "\nTime: " << ((double)clk) / CLOCKS_PER_SEC << "\n";
  return 0;
}

```