#include <bits/stdc++.h>
using namespace std;
class MPI {
 public:
  static complex<double> ca[(1 << 20)];
  static complex<double> cb[(1 << 20)];
  static complex<double> omega[(1 << 20)];
  static complex<double> dp[2][(1 << 20)];
  static complex<double> dat[(1 << 20)];
  static long long int p10[6 + 1];
  static long long int ratio;
  vector<long long int> value;
  bool sign;
  MPI(const string &s) {
    sign = false;
    if (s.size()) {
      sign = (s[0] == '-');
      int last = (s[0] == '-') ? 1 : 0;
      for (int i = s.size() - 1; last <= i; i -= 6) {
        long long int sum = 0;
        long long int base = 1;
        for (int j = 0; j < 6 && last <= i - j; j++) {
          sum += (s[i - j] - '0') * base;
          base *= 10;
        }
        value.push_back(sum);
      }
    }
    mpi_reform(*this);
  }
  MPI(long long int v) {
    sign = (v < 0);
    for (long long int t = abs(v); t; t /= 1000000)
      value.push_back(t % 1000000);
    if (value.size() == 0) value.push_back(0);
  }
  MPI(int v) {
    sign = (v < 0);
    for (long long int t = abs(v); t; t /= 1000000)
      value.push_back(t % 1000000);
    if (value.size() == 0) value.push_back(0);
  }
  MPI() {
    sign = false;
    value.push_back(0);
  }
  string to_string(bool ignore_sign = false) const {
    string res = "";
    for (int i = 0; i < value.size() - 1; i++) {
      for (long long int j = 0, t = value[i]; j < 6; j++) {
        res += string(1, '0' + t % 10);
        t /= 10;
      }
    }
    for (long long int t = value.back(); t; t /= 10)
      res += string(1, '0' + t % 10);
    reverse(res.begin(), res.end());
    if (res.size() == 0)
      res = "0";
    else if (sign && !ignore_sign)
      res = "-" + res;
    return res;
  }
  long long int to_long() const {
    long long int res = 0;
    long long int base = 1;
    for (int i = 0; i < value.size(); i++) {
      res += value[i] * base;
      base *= 1000000;
    }
    if (sign) res = -res;
    return res;
  }
  long long int size() const {
    long long int res = (value.size() - 1) * 6;
    int i = 0;
    for (; p10[i] <= value.back(); i++)
      ;
    return res + i;
  }
  static MPI mpi_abs_add(const MPI &m0, const MPI &m1) {
    MPI res = MPI();
    res.value.clear();
    long long int carry = 0;
    for (int i = 0; i < max(m0.value.size(), m1.value.size()); i++) {
      long long int t0 = (i < m0.value.size()) ? m0.value[i] : 0;
      long long int t1 = (i < m1.value.size()) ? m1.value[i] : 0;
      long long int t = t0 + t1 + carry;
      res.value.push_back(t % 1000000);
      carry = t / 1000000;
    }
    if (carry) res.value.push_back(carry);
    return res;
  }
  static MPI mpi_abs_sub_sub(const MPI &m0, const MPI &m1) {
    MPI res = MPI();
    res.value = m0.value;
    long long int carry = 0;
    for (int i = 0; i < m1.value.size(); i++) {
      res.value[i] -= carry;
      carry = 0;
      res.value[i] -= m1.value[i];
      if (res.value[i] < 0) {
        carry++;
        res.value[i] += 1000000;
      }
    }
    for (int i = m1.value.size(); carry; i++) {
      res.value[i] -= carry;
      carry = 0;
      if (res.value[i] < 0) {
        res.value[i] += 1000000;
        carry++;
      }
    }
    mpi_reform(res);
    return res;
  }
  static MPI mpi_abs_sub(const MPI &m0, const MPI &m1) {
    if (!mpi_abs_gt(m0, m1)) return mpi_abs_sub_sub(m0, m1);
    MPI res = mpi_abs_sub_sub(m1, m0);
    res.sign = !res.sign;
    return res;
  }
  void shift_left_value(const long long int p) {
    vector<long long int> vec = value;
    value = vector<long long int>(p, 0);
    for (int i = 0; i < vec.size(); i++) value.push_back(vec[i]);
  }
  void shift_right_value(const long long int p) {
    if (value.size() <= p) {
      value = vector<long long int>(1, 0);
      sign = false;
    } else {
      value.erase(value.begin(), value.begin() + p);
    }
  }
  static MPI mpi_newton_div(const MPI &m0, const MPI &m1, bool is_div) {
    MPI ans[2] = {0, 0};
    MPI p2 = MPI(2);
    int now = 0;
    int len = m0.value.size();
    int sum = len + m1.value.size();
    ans[now] = (long long int)1000000 * 1000000 / m1.value.back();
    ans[now].shift_left_value(len - 1);
    if (2 <= m0.value.size() && 2 <= m1.value.size()) {
      long long int lower =
          m1.value.back() * 1000000 + m1.value[m1.value.size() - 2];
      ans[now] = (long long int)1000000 * 1000000 * 1000000 / lower;
      ans[now].shift_left_value(len - 1);
    }
    p2.shift_left_value(sum);
    int cnt = 0;
    while (ans[0] != ans[1]) {
      int next = 1 - now;
      ans[next] = ans[now] * (p2 - mpi_abs_mul(m1, ans[now]));
      ans[next].shift_right_value(sum);
      now = next;
      if (cnt++ == 100)
        while (true)
          ;
    }
    ans[0] = mpi_abs_mul(ans[0], m0);
    ans[0].shift_right_value(sum);
    MPI rem = mpi_abs_sub(m0, mpi_abs_mul(ans[0], m1));
    for (; rem.sign; rem = mpi_abs_add(rem, m1)) ans[0]++;
    for (; !mpi_abs_sl(m1, rem); rem = mpi_abs_sub(rem, m1)) ans[0]--;
    if (is_div) return ans[0];
    return rem;
  }
  static void mpi_subst(MPI &from, const MPI &base, long long int cons,
                        long long int shift) {
    long long int carry = 0;
    for (long long int i = 0; i + shift < from.value.size(); i++) {
      from.value[shift + i] -= carry;
      carry = 0;
      if (i < base.value.size()) {
        carry = (base.value[i] * cons) / 1000000;
        from.value[shift + i] -= (base.value[i] * cons) % 1000000;
      }
      while (from.value[shift + i] < 0) {
        carry++;
        from.value[shift + i] += 1000000;
      }
    }
  }
  static bool mpi_can_sub(const MPI &from, const MPI &base, long long int cons,
                          long long int shift) {
    if (cons == 0) return true;
    long long int carry = 0;
    for (int i = 0; i < shift; i++)
      carry = carry * 1000000 + from.value[from.value.size() - i - 1];
    for (int i = 0; i < base.value.size(); i++) {
      if (cons * 1000000 < carry) return true;
      carry = carry * 1000000 + from.value[from.value.size() - shift - i - 1];
      carry -= base.value[base.value.size() - 1 - i] * cons;
      if (carry < 0) return false;
    }
    return true;
  }
  static MPI mpi_abs_div_small(const MPI &den, const MPI &num, bool is_div) {
    MPI ans, rem = den;
    ans.value = vector<long long int>(rem.value.size(), 0);
    long long int cons = abs(num.to_long()), carry = 0;
    for (long long int i = rem.value.size() - 1; 0 <= i; i--) {
      rem.value[i] += carry * 1000000;
      carry = rem.value[i] % cons;
      ans.value[i] = rem.value[i] / cons;
    }
    if (!is_div) return MPI(carry);
    mpi_reform(ans);
    return ans;
  }
  static MPI mpi_abs_div(const MPI &den, const MPI &num, bool is_div) {
    if (den < num && is_div) return MPI(0);
    if (den < num && !is_div) return den;
    long long int max_len = max(den.value.size(), num.value.size());
    long long int max_len_ratio = max_len * ratio;
    long long int log_num = log(max_len_ratio);
    long long int fool_cnt = den.value.size() * num.value.size();
    long long int newton_cnt = max_len_ratio * log_num * log_num;
    if (mpi_abs_gt(num, 1000000)) return mpi_abs_div_small(den, num, is_div);
    MPI ans(0);
    MPI rem = den;
    ans.value = vector<long long int>(rem.value.size(), 0);
    long long int num_pos = num.value.size() - 1;
    long long int num_n = num.value[num_pos];
    long long int base_shift = 0;
    if (num_n * 1000000 < 1000000000000000000ll / 1000000 && 1 <= num_pos) {
      num_n = num_n * 1000000 + num.value[--num_pos];
      base_shift++;
    }
    while (!mpi_abs_gt(rem, num)) {
      long long int rem_pos = rem.value.size() - 1;
      long long int rem_n = rem.value[rem_pos];
      long long int shift = 0;
      while (rem_n < num_n) {
        shift++;
        rem_n = rem_n * 1000000 + rem.value[--rem_pos];
      }
      long long int tmp = rem_n / num_n;
      long long int dif = rem_pos - num_pos;
      while (!mpi_can_sub(rem, num, tmp, shift - base_shift)) tmp--;
      if (tmp == 0) {
        rem_n = rem_n * 1000000 + rem.value[--rem_pos];
        tmp = rem_n / num_n;
        dif = rem_pos - num_pos;
        shift++;
        while (!mpi_can_sub(rem, num, tmp, shift - base_shift)) tmp--;
      }
      mpi_subst(rem, num, tmp, dif);
      ans.value[dif] += tmp;
      mpi_reform(rem);
    }
    if (!is_div) return rem;
    mpi_add_mul_reform(ans);
    return ans;
  }
  static void mpi_fft_init(int &N, int &MAX, int sum) {
    for (N = 1, MAX = 2; (1 << N) < sum; N++) MAX *= 2;
    MPI::omega[0] = complex<double>(1, 0);
    MPI::omega[1] =
        complex<double>(cos(2 * acos(-1) / MAX), -sin(2 * acos(-1) / MAX));
    for (int i = 2; i < MAX; i++) omega[i] = omega[i - 1] * omega[1];
  }
  static void mpi_fft(complex<double> *a, int &N, int &MAX) {
    int now = N & 1, bef = 1 - now, half = MAX >> 1;
    for (int i = 0; i < MAX; i++) dp[now][i] = a[i];
    for (int d = N - 1; 0 <= d; d--) {
      now = d & 1, bef = 1 - now;
      int S = 1 << d, K = MAX >> (d + 1);
      for (int s = 0; s < S; s++) {
        int omega_p = 0, sd = s + (1 << d);
        for (int k = 0; k < K; k++) {
          int index = s + (k << d);
          int other = index + half;
          complex<double> c0 = dp[bef][s + (k << (d + 1))];
          complex<double> c1 = omega[omega_p] * dp[bef][sd + (k << (d + 1))];
          dp[now][index] = c0 + c1;
          dp[now][other] = c0 - c1;
          omega_p += S;
          if (MAX < omega_p) omega_p -= S;
        }
      }
    }
  }
  static MPI mpi_fool_mul(const MPI &m0, const MPI &m1) {
    MPI res;
    int length = m0.value.size() + m1.value.size();
    res.value = vector<long long int>(length, 0);
    for (int i = 0; i < m0.value.size(); i++)
      if (m0.value[i]) {
        for (int j = 0; j < m1.value.size(); j++) {
          res.value[i + j] += m0.value[i] * m1.value[j];
        }
      }
    long long int carry = 0;
    for (int i = 0; i < length; i++) {
      res.value[i] += carry;
      carry = res.value[i] / 1000000;
      res.value[i] %= 1000000;
    }
    for (; carry; carry /= 1000000) res.value.push_back(carry % 1000000);
    mpi_reform(res);
    return res;
  }
  static MPI mpi_abs_mul(const MPI &m0, const MPI &m1) {
    long long int max_len = max(m0.value.size(), m1.value.size());
    long long int max_len_ratio = max_len * ratio;
    long long int fool_cnt = m0.value.size() * m1.value.size();
    long long int fft_cnt = max_len_ratio * log(max_len_ratio);
    if (fool_cnt < (fft_cnt + 1) * 28) return mpi_fool_mul(m0, m1);
    cout << "FFT!" << endl;
    int n, MAX, sum = (m0.size() + m1.size()) / 2 + 1;
    mpi_fft_init(n, MAX, sum);
    memset(ca, 0, sizeof(complex<double>) * MAX);
    memset(cb, 0, sizeof(complex<double>) * MAX);
    for (int i = 0; i < m0.value.size(); i++) {
      long long int t = m0.value[i];
      for (int j = 0; j < ratio && i * ratio + j < MAX; j++) {
        ca[i * ratio + j] = complex<double>(t % 100, 0);
        t /= 100;
      }
    }
    for (int i = 0; i < m1.value.size(); i++) {
      long long int t = m1.value[i];
      for (int j = 0; j < ratio && i * ratio + j < MAX; j++) {
        cb[i * ratio + j] = complex<double>(t % 100, 0);
        t /= 100;
      }
    }
    mpi_fft(ca, n, MAX);
    memcpy(ca, dp[0], sizeof(complex<double>) * MAX);
    mpi_fft(cb, n, MAX);
    for (int i = 0; i < MAX; i++) ca[i] *= dp[0][i];
    for (int i = 1; i < MAX / 2; i++) swap(omega[i], omega[MAX - i]);
    mpi_fft(ca, n, MAX);
    double inverse = 1.0 / MAX;
    for (int i = 0; i < MAX; i++) dp[0][i] *= inverse;
    MPI res;
    res.value.clear();
    vector<long long int> bases(1, 1);
    for (int i = 1; i < ratio; i++) bases.push_back(bases.back() * 100);
    for (int i = 0; i * ratio < MAX; i++) {
      long long int t = 0;
      for (int j = 0; i * ratio + j < MAX && j < ratio; j++) {
        t += (long long int)(dp[0][i * ratio + j].real() + 0.5) * bases[j];
      }
      res.value.push_back(t);
    }
    long long int carry = 0;
    for (int i = 0; i < res.value.size(); i++) {
      res.value[i] += carry;
      carry = res.value[i] / 1000000;
      res.value[i] %= 1000000;
    }
    for (; carry; carry /= 1000000) res.value.push_back(carry % 1000000);
    mpi_reform(res);
    return res;
  }
  static bool mpi_abs_gt(const MPI &m0, const MPI &m1) {
    if (m0.value.size() != m1.value.size())
      return m0.value.size() < m1.value.size();
    for (int i = m0.value.size() - 1; 0 <= i; i--) {
      if (m0.value[i] != m1.value[i]) return m0.value[i] < m1.value[i];
    }
    return false;
  }
  static bool mpi_abs_sl(const MPI &m0, const MPI &m1) {
    if (m0.value.size() != m1.value.size())
      return m0.value.size() > m1.value.size();
    for (int i = m0.value.size() - 1; 0 <= i; i--) {
      if (m0.value[i] != m1.value[i]) return m0.value[i] > m1.value[i];
    }
    return false;
  }
  static bool mpi_abs_eq(const MPI &m0, const MPI &m1) {
    if (m0.value.size() != m1.value.size()) return false;
    for (int i = 0; i < m0.value.size(); i++) {
      if (m0.value[i] != m1.value[i]) return false;
    }
    return true;
  }
  MPI operator+(const MPI &mpi) const {
    bool b0 = sign, b1 = mpi.sign;
    if (!b0 && !b1) return mpi_abs_add(*this, mpi);
    if (!b0 && b1) return mpi_abs_sub(*this, mpi);
    if (b0 && !b1) return mpi_abs_sub(mpi, *this);
    MPI res = mpi_abs_add(*this, mpi);
    res.sign = !res.sign;
    return res;
  }
  MPI operator-(const MPI &mpi) const {
    bool b0 = sign, b1 = mpi.sign;
    if (!b0 && !b1) return mpi_abs_sub(*this, mpi);
    if (!b0 && b1) return mpi_abs_add(*this, mpi);
    if (b0 && b1) return mpi_abs_sub(mpi, *this);
    MPI res = mpi_abs_add(*this, mpi);
    res.sign = !res.sign;
    return res;
  }
  inline MPI operator*(const MPI &mpi) const {
    MPI res = mpi_abs_mul(*this, mpi);
    if (sign != mpi.sign) res.sign = !res.sign;
    return res;
  }
  inline MPI operator/(const MPI &mpi) const {
    MPI res = mpi_abs_div(*this, mpi, true);
    if (sign != mpi.sign) res.sign = !res.sign;
    return res;
  }
  inline MPI operator%(const MPI &mpi) const {
    MPI res = mpi_abs_div(*this, mpi, false);
    if (sign) res.sign = !res.sign;
    return res;
  }
  bool operator<(const MPI &mpi) const {
    if (value.size() == 1 && value[0] == 0 && mpi.value.size() == 1 &&
        mpi.value[0] == 0)
      return false;
    bool b0 = sign, b1 = mpi.sign;
    if (!b0 && b1) return false;
    if (b0 && !b1) return true;
    if (!b0 && !b1) return mpi_abs_gt(*this, mpi);
    if (b0 && b1) return mpi_abs_sl(*this, mpi);
  }
  bool operator>(const MPI &mpi) const {
    if (value.size() == 1 && value[0] == 0 && mpi.value.size() == 1 &&
        mpi.value[0] == 0)
      return false;
    bool b0 = sign, b1 = mpi.sign;
    if (!b0 && b1) return true;
    if (b0 && !b1) return false;
    if (!b0 && !b1) return mpi_abs_sl(*this, mpi);
    if (b0 && b1) return mpi_abs_gt(*this, mpi);
  }
  inline bool operator==(const MPI &mpi) const {
    if (value.size() == 1 && value[0] == 0 && mpi.value.size() == 1 &&
        mpi.value[0] == 0)
      return true;
    if (sign != mpi.sign) return false;
    return mpi_abs_eq(*this, mpi);
  }
  inline bool operator>=(const MPI &mpi) const { return !(*this < mpi); }
  inline bool operator<=(const MPI &mpi) const { return !(*this > mpi); }
  inline bool operator!=(const MPI &mpi) const { return !(*this == mpi); }
  inline void operator+=(const MPI &mpi) { *this = *this + mpi; }
  inline void operator-=(const MPI &mpi) { *this = *this - mpi; }
  inline void operator*=(const MPI &mpi) { *this = *this * mpi; }
  inline void operator/=(const MPI &mpi) { *this = *this / mpi; }
  inline void operator%=(const MPI &mpi) { *this = *this % mpi; }
  inline friend bool operator>(long long int l, const MPI &mpi) {
    return MPI(l) > mpi;
  }
  inline friend bool operator<(long long int l, const MPI &mpi) {
    return MPI(l) < mpi;
  }
  inline friend bool operator>=(long long int l, const MPI &mpi) {
    return MPI(l) >= mpi;
  }
  inline friend bool operator<=(long long int l, const MPI &mpi) {
    return MPI(l) <= mpi;
  }
  inline friend bool operator!=(long long int l, const MPI &mpi) {
    return MPI(l) != mpi;
  }
  inline friend bool operator==(long long int l, const MPI &mpi) {
    return MPI(l) == mpi;
  }
  inline MPI operator--() {
    *this = *this - MPI(1);
    return *this;
  }
  inline MPI operator++() {
    *this = *this + MPI(1);
    return *this;
  }
  inline MPI operator++(int i) {
    MPI res = *this;
    *this = *this + MPI(1);
    return res;
  }
  inline MPI operator--(int i) {
    MPI res = *this;
    *this = *this + MPI(1);
    return res;
  }
  inline MPI operator-() {
    MPI res = *this;
    res.sign = !res.sign;
    return res;
  }
  inline friend std::ostream &operator<<(std::ostream &os, const MPI &mpi) {
    os << mpi.to_string();
    return os;
  }
  inline friend std::istream &operator>>(std::istream &is, MPI &mpi) {
    string str;
    is >> str;
    mpi = MPI(str);
    return is;
  }

 private:
  static void mpi_add_mul_reform_vec(vector<long long int> &vec) {
    long long int carry = 0;
    for (int i = 0; i < vec.size(); i++) {
      vec[i] += carry;
      carry = vec[i] / 1000000;
      vec[i] %= 1000000;
    }
    for (; carry; carry /= 1000000) vec.push_back(carry % 1000000);
    mpi_reform_vec(vec);
  }
  inline static void mpi_add_mul_reform(MPI &mpi) {
    mpi_add_mul_reform_vec(mpi.value);
  }
  static void mpi_reform_vec(vector<long long int> &vec) {
    if (vec.size() == 0) vec.push_back(0);
    while (1 < vec.size() && vec.back() == 0) vec.pop_back();
  }
  inline static void mpi_reform(MPI &mpi) { mpi_reform_vec(mpi.value); }
};
complex<double> MPI::ca[(1 << 20)];
complex<double> MPI::cb[(1 << 20)];
complex<double> MPI::omega[(1 << 20)];
complex<double> MPI::dp[2][(1 << 20)];
complex<double> MPI::dat[(1 << 20)];
long long int MPI::p10[6 + 1] = {1, 10, 100, 1000, 10000, 100000, 1000000};
long long int MPI::ratio = 6 / 2;
class IRN {
 public:
  MPI IRN_DEN;
  MPI IRN_NUM;
  bool IRN_SIGN;
  IRN() {
    IRN_DEN = 0;
    IRN_NUM = 1;
    IRN_SIGN = false;
  }
  IRN(string irn_str0, string irn_str1) {
    IRN_DEN = irn_str0;
    IRN_NUM = irn_str1;
    IRN_SIGN = false;
    if (IRN_DEN < 0) IRN_SIGN = !IRN_SIGN;
    if (IRN_NUM < 0) IRN_SIGN = !IRN_SIGN;
    IRN_DEN.sign = false;
    IRN_NUM.sign = false;
    irn_reduct(*this);
  }
  IRN(long long int irn_li0, long long int irn_li1) {
    IRN_DEN = irn_li0;
    IRN_NUM = irn_li1;
    IRN_SIGN = false;
    if (IRN_DEN < 0) IRN_SIGN = !IRN_SIGN;
    if (IRN_NUM < 0) IRN_SIGN = !IRN_SIGN;
    IRN_DEN.sign = false;
    IRN_NUM.sign = false;
    irn_reduct(*this);
  }
  IRN(long long int irn_li) {
    IRN_DEN = irn_li;
    IRN_NUM = 1;
    IRN_SIGN = false;
  }
  IRN(string irn_str) {
    IRN_DEN = irn_str;
    IRN_NUM = 1;
    IRN_SIGN = false;
  }
  IRN(MPI mpi0, MPI mpi1) {
    IRN_DEN = mpi0;
    IRN_NUM = mpi1;
    IRN_SIGN = false;
  }
  string to_string() const {
    if (IRN_SIGN && IRN_DEN != 0)
      return "-" + IRN_DEN.to_string() + "/" + IRN_NUM.to_string();
    return IRN_DEN.to_string() + "/" + IRN_NUM.to_string();
  }
  static MPI irn_mpi_gcd(MPI mpi0, MPI mpi1) {
    if (mpi1 == 0) return 1;
    if (mpi0 % mpi1 == 0) return mpi1;
    return irn_mpi_gcd(mpi1, mpi0 % mpi1);
  }
  void irn_reduct(IRN &irn_var, bool only_sign = false) const {
    if (irn_var.IRN_DEN == 0) {
      irn_var.IRN_NUM = 1;
      irn_var.IRN_SIGN = false;
      return;
    }
    if (irn_var.IRN_DEN < 0) irn_var.IRN_SIGN = !irn_var.IRN_SIGN;
    if (irn_var.IRN_NUM < 0) irn_var.IRN_SIGN = !irn_var.IRN_SIGN;
    irn_var.IRN_DEN.sign = false;
    irn_var.IRN_NUM.sign = false;
    if (only_sign) return;
    MPI irn_t = irn_mpi_gcd(irn_var.IRN_NUM, irn_var.IRN_DEN);
    irn_var.IRN_NUM /= irn_t;
    irn_var.IRN_DEN /= irn_t;
  }
  IRN irn_mul(const IRN &irn0, const IRN &irn1) const {
    IRN irn_res(1, 1);
    MPI irn_t = irn_mpi_gcd(irn0.IRN_DEN, irn1.IRN_NUM);
    irn_res.IRN_DEN = irn0.IRN_DEN / irn_t;
    irn_res.IRN_NUM = irn1.IRN_NUM / irn_t;
    irn_t = irn_mpi_gcd(irn0.IRN_NUM, irn1.IRN_DEN);
    irn_res.IRN_DEN *= irn1.IRN_DEN / irn_t;
    irn_res.IRN_NUM *= irn0.IRN_NUM / irn_t;
    if (irn1.IRN_SIGN) irn_res.IRN_SIGN = !irn_res.IRN_SIGN;
    if (irn0.IRN_SIGN) irn_res.IRN_SIGN = !irn_res.IRN_SIGN;
    if (irn_res.IRN_DEN == 0) {
      irn_res.IRN_NUM = 1;
      irn_res.IRN_SIGN = false;
    }
    return irn_res;
  }
  IRN irn_div(const IRN &irn0, const IRN &irn1) const {
    IRN irn_res(1, 1);
    MPI irn_t = irn_mpi_gcd(irn0.IRN_DEN, irn1.IRN_DEN);
    irn_res.IRN_DEN = irn0.IRN_DEN / irn_t;
    irn_res.IRN_NUM = irn1.IRN_DEN / irn_t;
    irn_t = irn_mpi_gcd(irn0.IRN_NUM, irn1.IRN_NUM);
    irn_res.IRN_DEN *= irn1.IRN_NUM / irn_t;
    irn_res.IRN_NUM *= irn0.IRN_NUM / irn_t;
    if (irn1.IRN_SIGN) irn_res.IRN_SIGN = !irn_res.IRN_SIGN;
    if (irn0.IRN_SIGN) irn_res.IRN_SIGN = !irn_res.IRN_SIGN;
    if (irn_res.IRN_DEN == 0) {
      irn_res.IRN_NUM = 1;
      irn_res.IRN_SIGN = false;
    }
    return irn_res;
  }
  IRN irn_abs_add(const IRN &irn0, const IRN &irn1) const {
    IRN irn_res(0);
    if (irn0.IRN_NUM == irn1.IRN_NUM) {
      irn_res.IRN_DEN = irn0.IRN_DEN + irn1.IRN_DEN;
      irn_res.IRN_NUM = irn0.IRN_NUM;
    } else {
      irn_res.IRN_NUM = irn0.IRN_NUM * irn1.IRN_NUM;
      irn_res.IRN_DEN = irn0.IRN_DEN * irn1.IRN_NUM;
      irn_res.IRN_DEN += irn1.IRN_DEN * irn0.IRN_NUM;
    }
    irn_reduct(irn_res, irn0.IRN_NUM == 1 || irn1.IRN_NUM == 1);
    return irn_res;
  }
  IRN irn_abs_sub(const IRN &irn0, const IRN &irn1) const {
    IRN irn_res(0);
    if (irn0.IRN_NUM == irn1.IRN_NUM) {
      irn_res.IRN_DEN = irn0.IRN_DEN - irn1.IRN_DEN;
      irn_res.IRN_NUM = irn0.IRN_NUM;
    } else {
      irn_res.IRN_NUM = irn0.IRN_NUM * irn1.IRN_NUM;
      irn_res.IRN_DEN = irn0.IRN_DEN * irn1.IRN_NUM;
      irn_res.IRN_DEN -= irn1.IRN_DEN * irn0.IRN_NUM;
    }
    irn_reduct(irn_res, irn0.IRN_NUM == 0 || irn1.IRN_NUM == 0);
    return irn_res;
  }
  IRN irn_add(const IRN &irn0, const IRN &irn1) const {
    if (irn0.IRN_SIGN && irn1.IRN_SIGN) {
      IRN irn_res = irn_abs_add(irn0, irn1);
      irn_res.IRN_SIGN = !irn_res.IRN_SIGN;
      return irn_res;
    }
    if (!irn0.IRN_SIGN && !irn1.IRN_SIGN) return irn_abs_add(irn0, irn1);
    IRN irn_res;
    if (!irn0.IRN_SIGN && irn1.IRN_SIGN) irn_res = irn_abs_sub(irn0, irn1);
    if (irn0.IRN_SIGN && !irn1.IRN_SIGN) irn_res = irn_abs_sub(irn1, irn0);
    if (irn_res.IRN_DEN < 0) {
      irn_res.IRN_DEN.sign = false;
      irn_res.IRN_SIGN = true;
    }
    return irn_res;
  }
  IRN irn_sub(const IRN &irn0, const IRN &irn1) const {
    if (!irn0.IRN_SIGN && irn1.IRN_SIGN) return irn_abs_add(irn0, irn1);
    if (irn0.IRN_SIGN && !irn1.IRN_SIGN) {
      IRN irn_res = irn_abs_add(irn0, irn1);
      irn_res.IRN_SIGN = !irn_res.IRN_SIGN;
      return irn_res;
    }
    IRN irn_res;
    if (irn0.IRN_SIGN && irn1.IRN_SIGN) {
      irn_res = irn_abs_sub(irn0, irn1);
      irn_res.IRN_SIGN = !irn_res.IRN_SIGN;
    }
    if (!irn0.IRN_SIGN && !irn1.IRN_SIGN) {
      irn_res = irn_abs_sub(irn0, irn1);
    }
    if (irn_res.IRN_DEN < 0) {
      irn_res.IRN_DEN.sign = false;
      irn_res.IRN_SIGN = true;
    }
    return irn_res;
  }
  bool operator<(const IRN &irn_var) const {
    if (this->IRN_DEN == 0 && irn_var.IRN_DEN == 0) return false;
    bool b0 = this->IRN_SIGN, b1 = irn_var.IRN_SIGN;
    if (b0 && !b1) return true;
    if (!b1 && b0) return false;
    MPI left = this->IRN_DEN * irn_var.IRN_NUM;
    MPI right = irn_var.IRN_DEN * this->IRN_NUM;
    if (!b0 && !b1) return left < right;
    return right < left;
  }
  bool operator>(const IRN &irn_var) const {
    if (this->IRN_DEN == 0 && irn_var.IRN_DEN == 0) return false;
    bool b0 = this->IRN_SIGN, b1 = irn_var.IRN_SIGN;
    if (b0 && !b1) return false;
    if (!b0 && b1) return true;
    MPI left = this->IRN_DEN * irn_var.IRN_NUM;
    MPI right = irn_var.IRN_DEN * this->IRN_NUM;
    if (!b0 && !b1) return left > right;
    return right < left;
  }
  bool operator==(const IRN &irn_var) const {
    if (this->IRN_DEN == 0 && irn_var.IRN_DEN == 0) return true;
    if (this->IRN_SIGN && !irn_var.IRN_SIGN) return false;
    if (!this->IRN_SIGN && irn_var.IRN_SIGN) return false;
    return this->IRN_DEN == irn_var.IRN_DEN && this->IRN_NUM == irn_var.IRN_NUM;
  }
  IRN operator+(const IRN &irn_var) const { return irn_add(*this, irn_var); }
  IRN operator-(const IRN &irn_var) const { return irn_sub(*this, irn_var); }
  IRN operator/(const IRN &irn_var) const { return irn_div(*this, irn_var); }
  IRN operator*(const IRN &irn_var) const { return irn_mul(*this, irn_var); }
  void operator+=(const IRN &irn_var) { *this = *this + irn_var; }
  void operator-=(const IRN &irn_var) { *this = *this - irn_var; }
  void operator*=(const IRN &irn_var) { *this = *this * irn_var; }
  void operator/=(const IRN &irn_var) { *this = *this / irn_var; }
  IRN operator<=(const IRN &irn_var) const { return !(irn_var < *this); }
  IRN operator>=(const IRN &irn_var) const { return !(*this < irn_var); }
  IRN operator!=(const IRN &irn_var) const { return !(*this == irn_var); }
  friend std::ostream &operator<<(std::ostream &os, const IRN &irn_var) {
    os << irn_var.to_string();
    return os;
  }

 private:
};
MPI N = 2;
long long int n;
IRN recur(long long int m, int cnt = 0) {
  if (m == 0)
    while (true)
      ;
  if (m == 1) return 0;
  N *= 2;
  m *= 2;
  if (m < n)
    return IRN(1, 1) + recur(m, cnt + 1);
  else
    return IRN(1, 1) + IRN(m - n, m) * recur(m - n, cnt + 1);
}
int main() {
  cin >> n;
  long long int shift = 0;
  for (; n % 2 == 0; n /= 2) shift++;
  if (n == 1) {
    cout << shift << "/1" << endl;
    return 0;
  }
  IRN res = IRN(1, 1) + recur(2);
  res *= IRN(N, N - 1);
  res += shift;
  cout << res << endl;
}

### Prompt

Please create a solution in Cpp to the following problem:

This is the modification of the problem used during the official round. Unfortunately, author's solution of the original problem appeared wrong, so the problem was changed specially for the archive.

Once upon a time in a far away kingdom lived the King. The King had a beautiful daughter, Victoria. They lived happily, but not happily ever after: one day a vicious dragon attacked the kingdom and stole Victoria. The King was full of grief, yet he gathered his noble knights and promised half of his kingdom and Victoria's hand in marriage to the one who will save the girl from the infernal beast.

Having travelled for some time, the knights found the dragon's lair and all of them rushed there to save Victoria. Each knight spat on the dragon once and, as the dragon had quite a fragile and frail heart, his heart broke and poor beast died. As for the noble knights, they got Victoria right to the King and started brawling as each one wanted the girl's hand in marriage.

The problem was that all the noble knights were equally noble and equally handsome, and Victoria didn't want to marry any of them anyway. Then the King (and he was a very wise man and didn't want to hurt anybody's feelings) decided to find out who will get his daughter randomly, i.e. tossing a coin. However, there turned out to be n noble knights and the coin only has two sides. The good thing is that when a coin is tossed, the coin falls on each side with equal probability. The King got interested how to pick one noble knight using this coin so that all knights had equal probability of being chosen (the probability in that case should always be equal to 1 / n). First the King wants to know the expected number of times he will need to toss a coin to determine the winner. Besides, while tossing the coin, the King should follow the optimal tossing strategy (i.e. the strategy that minimizes the expected number of tosses). Help the King in this challenging task.

Input

The first line contains a single integer n from the problem's statement (1 ≤ n ≤ 10000).

Output

Print the sought expected number of tosses as an irreducible fraction in the following form: "a/b" (without the quotes) without leading zeroes.

Examples

Input

2


Output

1/1


Input

3


Output

8/3


Input

4


Output

2/1

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
class MPI {
 public:
  static complex<double> ca[(1 << 20)];
  static complex<double> cb[(1 << 20)];
  static complex<double> omega[(1 << 20)];
  static complex<double> dp[2][(1 << 20)];
  static complex<double> dat[(1 << 20)];
  static long long int p10[6 + 1];
  static long long int ratio;
  vector<long long int> value;
  bool sign;
  MPI(const string &s) {
    sign = false;
    if (s.size()) {
      sign = (s[0] == '-');
      int last = (s[0] == '-') ? 1 : 0;
      for (int i = s.size() - 1; last <= i; i -= 6) {
        long long int sum = 0;
        long long int base = 1;
        for (int j = 0; j < 6 && last <= i - j; j++) {
          sum += (s[i - j] - '0') * base;
          base *= 10;
        }
        value.push_back(sum);
      }
    }
    mpi_reform(*this);
  }
  MPI(long long int v) {
    sign = (v < 0);
    for (long long int t = abs(v); t; t /= 1000000)
      value.push_back(t % 1000000);
    if (value.size() == 0) value.push_back(0);
  }
  MPI(int v) {
    sign = (v < 0);
    for (long long int t = abs(v); t; t /= 1000000)
      value.push_back(t % 1000000);
    if (value.size() == 0) value.push_back(0);
  }
  MPI() {
    sign = false;
    value.push_back(0);
  }
  string to_string(bool ignore_sign = false) const {
    string res = "";
    for (int i = 0; i < value.size() - 1; i++) {
      for (long long int j = 0, t = value[i]; j < 6; j++) {
        res += string(1, '0' + t % 10);
        t /= 10;
      }
    }
    for (long long int t = value.back(); t; t /= 10)
      res += string(1, '0' + t % 10);
    reverse(res.begin(), res.end());
    if (res.size() == 0)
      res = "0";
    else if (sign && !ignore_sign)
      res = "-" + res;
    return res;
  }
  long long int to_long() const {
    long long int res = 0;
    long long int base = 1;
    for (int i = 0; i < value.size(); i++) {
      res += value[i] * base;
      base *= 1000000;
    }
    if (sign) res = -res;
    return res;
  }
  long long int size() const {
    long long int res = (value.size() - 1) * 6;
    int i = 0;
    for (; p10[i] <= value.back(); i++)
      ;
    return res + i;
  }
  static MPI mpi_abs_add(const MPI &m0, const MPI &m1) {
    MPI res = MPI();
    res.value.clear();
    long long int carry = 0;
    for (int i = 0; i < max(m0.value.size(), m1.value.size()); i++) {
      long long int t0 = (i < m0.value.size()) ? m0.value[i] : 0;
      long long int t1 = (i < m1.value.size()) ? m1.value[i] : 0;
      long long int t = t0 + t1 + carry;
      res.value.push_back(t % 1000000);
      carry = t / 1000000;
    }
    if (carry) res.value.push_back(carry);
    return res;
  }
  static MPI mpi_abs_sub_sub(const MPI &m0, const MPI &m1) {
    MPI res = MPI();
    res.value = m0.value;
    long long int carry = 0;
    for (int i = 0; i < m1.value.size(); i++) {
      res.value[i] -= carry;
      carry = 0;
      res.value[i] -= m1.value[i];
      if (res.value[i] < 0) {
        carry++;
        res.value[i] += 1000000;
      }
    }
    for (int i = m1.value.size(); carry; i++) {
      res.value[i] -= carry;
      carry = 0;
      if (res.value[i] < 0) {
        res.value[i] += 1000000;
        carry++;
      }
    }
    mpi_reform(res);
    return res;
  }
  static MPI mpi_abs_sub(const MPI &m0, const MPI &m1) {
    if (!mpi_abs_gt(m0, m1)) return mpi_abs_sub_sub(m0, m1);
    MPI res = mpi_abs_sub_sub(m1, m0);
    res.sign = !res.sign;
    return res;
  }
  void shift_left_value(const long long int p) {
    vector<long long int> vec = value;
    value = vector<long long int>(p, 0);
    for (int i = 0; i < vec.size(); i++) value.push_back(vec[i]);
  }
  void shift_right_value(const long long int p) {
    if (value.size() <= p) {
      value = vector<long long int>(1, 0);
      sign = false;
    } else {
      value.erase(value.begin(), value.begin() + p);
    }
  }
  static MPI mpi_newton_div(const MPI &m0, const MPI &m1, bool is_div) {
    MPI ans[2] = {0, 0};
    MPI p2 = MPI(2);
    int now = 0;
    int len = m0.value.size();
    int sum = len + m1.value.size();
    ans[now] = (long long int)1000000 * 1000000 / m1.value.back();
    ans[now].shift_left_value(len - 1);
    if (2 <= m0.value.size() && 2 <= m1.value.size()) {
      long long int lower =
          m1.value.back() * 1000000 + m1.value[m1.value.size() - 2];
      ans[now] = (long long int)1000000 * 1000000 * 1000000 / lower;
      ans[now].shift_left_value(len - 1);
    }
    p2.shift_left_value(sum);
    int cnt = 0;
    while (ans[0] != ans[1]) {
      int next = 1 - now;
      ans[next] = ans[now] * (p2 - mpi_abs_mul(m1, ans[now]));
      ans[next].shift_right_value(sum);
      now = next;
      if (cnt++ == 100)
        while (true)
          ;
    }
    ans[0] = mpi_abs_mul(ans[0], m0);
    ans[0].shift_right_value(sum);
    MPI rem = mpi_abs_sub(m0, mpi_abs_mul(ans[0], m1));
    for (; rem.sign; rem = mpi_abs_add(rem, m1)) ans[0]++;
    for (; !mpi_abs_sl(m1, rem); rem = mpi_abs_sub(rem, m1)) ans[0]--;
    if (is_div) return ans[0];
    return rem;
  }
  static void mpi_subst(MPI &from, const MPI &base, long long int cons,
                        long long int shift) {
    long long int carry = 0;
    for (long long int i = 0; i + shift < from.value.size(); i++) {
      from.value[shift + i] -= carry;
      carry = 0;
      if (i < base.value.size()) {
        carry = (base.value[i] * cons) / 1000000;
        from.value[shift + i] -= (base.value[i] * cons) % 1000000;
      }
      while (from.value[shift + i] < 0) {
        carry++;
        from.value[shift + i] += 1000000;
      }
    }
  }
  static bool mpi_can_sub(const MPI &from, const MPI &base, long long int cons,
                          long long int shift) {
    if (cons == 0) return true;
    long long int carry = 0;
    for (int i = 0; i < shift; i++)
      carry = carry * 1000000 + from.value[from.value.size() - i - 1];
    for (int i = 0; i < base.value.size(); i++) {
      if (cons * 1000000 < carry) return true;
      carry = carry * 1000000 + from.value[from.value.size() - shift - i - 1];
      carry -= base.value[base.value.size() - 1 - i] * cons;
      if (carry < 0) return false;
    }
    return true;
  }
  static MPI mpi_abs_div_small(const MPI &den, const MPI &num, bool is_div) {
    MPI ans, rem = den;
    ans.value = vector<long long int>(rem.value.size(), 0);
    long long int cons = abs(num.to_long()), carry = 0;
    for (long long int i = rem.value.size() - 1; 0 <= i; i--) {
      rem.value[i] += carry * 1000000;
      carry = rem.value[i] % cons;
      ans.value[i] = rem.value[i] / cons;
    }
    if (!is_div) return MPI(carry);
    mpi_reform(ans);
    return ans;
  }
  static MPI mpi_abs_div(const MPI &den, const MPI &num, bool is_div) {
    if (den < num && is_div) return MPI(0);
    if (den < num && !is_div) return den;
    long long int max_len = max(den.value.size(), num.value.size());
    long long int max_len_ratio = max_len * ratio;
    long long int log_num = log(max_len_ratio);
    long long int fool_cnt = den.value.size() * num.value.size();
    long long int newton_cnt = max_len_ratio * log_num * log_num;
    if (mpi_abs_gt(num, 1000000)) return mpi_abs_div_small(den, num, is_div);
    MPI ans(0);
    MPI rem = den;
    ans.value = vector<long long int>(rem.value.size(), 0);
    long long int num_pos = num.value.size() - 1;
    long long int num_n = num.value[num_pos];
    long long int base_shift = 0;
    if (num_n * 1000000 < 1000000000000000000ll / 1000000 && 1 <= num_pos) {
      num_n = num_n * 1000000 + num.value[--num_pos];
      base_shift++;
    }
    while (!mpi_abs_gt(rem, num)) {
      long long int rem_pos = rem.value.size() - 1;
      long long int rem_n = rem.value[rem_pos];
      long long int shift = 0;
      while (rem_n < num_n) {
        shift++;
        rem_n = rem_n * 1000000 + rem.value[--rem_pos];
      }
      long long int tmp = rem_n / num_n;
      long long int dif = rem_pos - num_pos;
      while (!mpi_can_sub(rem, num, tmp, shift - base_shift)) tmp--;
      if (tmp == 0) {
        rem_n = rem_n * 1000000 + rem.value[--rem_pos];
        tmp = rem_n / num_n;
        dif = rem_pos - num_pos;
        shift++;
        while (!mpi_can_sub(rem, num, tmp, shift - base_shift)) tmp--;
      }
      mpi_subst(rem, num, tmp, dif);
      ans.value[dif] += tmp;
      mpi_reform(rem);
    }
    if (!is_div) return rem;
    mpi_add_mul_reform(ans);
    return ans;
  }
  static void mpi_fft_init(int &N, int &MAX, int sum) {
    for (N = 1, MAX = 2; (1 << N) < sum; N++) MAX *= 2;
    MPI::omega[0] = complex<double>(1, 0);
    MPI::omega[1] =
        complex<double>(cos(2 * acos(-1) / MAX), -sin(2 * acos(-1) / MAX));
    for (int i = 2; i < MAX; i++) omega[i] = omega[i - 1] * omega[1];
  }
  static void mpi_fft(complex<double> *a, int &N, int &MAX) {
    int now = N & 1, bef = 1 - now, half = MAX >> 1;
    for (int i = 0; i < MAX; i++) dp[now][i] = a[i];
    for (int d = N - 1; 0 <= d; d--) {
      now = d & 1, bef = 1 - now;
      int S = 1 << d, K = MAX >> (d + 1);
      for (int s = 0; s < S; s++) {
        int omega_p = 0, sd = s + (1 << d);
        for (int k = 0; k < K; k++) {
          int index = s + (k << d);
          int other = index + half;
          complex<double> c0 = dp[bef][s + (k << (d + 1))];
          complex<double> c1 = omega[omega_p] * dp[bef][sd + (k << (d + 1))];
          dp[now][index] = c0 + c1;
          dp[now][other] = c0 - c1;
          omega_p += S;
          if (MAX < omega_p) omega_p -= S;
        }
      }
    }
  }
  static MPI mpi_fool_mul(const MPI &m0, const MPI &m1) {
    MPI res;
    int length = m0.value.size() + m1.value.size();
    res.value = vector<long long int>(length, 0);
    for (int i = 0; i < m0.value.size(); i++)
      if (m0.value[i]) {
        for (int j = 0; j < m1.value.size(); j++) {
          res.value[i + j] += m0.value[i] * m1.value[j];
        }
      }
    long long int carry = 0;
    for (int i = 0; i < length; i++) {
      res.value[i] += carry;
      carry = res.value[i] / 1000000;
      res.value[i] %= 1000000;
    }
    for (; carry; carry /= 1000000) res.value.push_back(carry % 1000000);
    mpi_reform(res);
    return res;
  }
  static MPI mpi_abs_mul(const MPI &m0, const MPI &m1) {
    long long int max_len = max(m0.value.size(), m1.value.size());
    long long int max_len_ratio = max_len * ratio;
    long long int fool_cnt = m0.value.size() * m1.value.size();
    long long int fft_cnt = max_len_ratio * log(max_len_ratio);
    if (fool_cnt < (fft_cnt + 1) * 28) return mpi_fool_mul(m0, m1);
    cout << "FFT!" << endl;
    int n, MAX, sum = (m0.size() + m1.size()) / 2 + 1;
    mpi_fft_init(n, MAX, sum);
    memset(ca, 0, sizeof(complex<double>) * MAX);
    memset(cb, 0, sizeof(complex<double>) * MAX);
    for (int i = 0; i < m0.value.size(); i++) {
      long long int t = m0.value[i];
      for (int j = 0; j < ratio && i * ratio + j < MAX; j++) {
        ca[i * ratio + j] = complex<double>(t % 100, 0);
        t /= 100;
      }
    }
    for (int i = 0; i < m1.value.size(); i++) {
      long long int t = m1.value[i];
      for (int j = 0; j < ratio && i * ratio + j < MAX; j++) {
        cb[i * ratio + j] = complex<double>(t % 100, 0);
        t /= 100;
      }
    }
    mpi_fft(ca, n, MAX);
    memcpy(ca, dp[0], sizeof(complex<double>) * MAX);
    mpi_fft(cb, n, MAX);
    for (int i = 0; i < MAX; i++) ca[i] *= dp[0][i];
    for (int i = 1; i < MAX / 2; i++) swap(omega[i], omega[MAX - i]);
    mpi_fft(ca, n, MAX);
    double inverse = 1.0 / MAX;
    for (int i = 0; i < MAX; i++) dp[0][i] *= inverse;
    MPI res;
    res.value.clear();
    vector<long long int> bases(1, 1);
    for (int i = 1; i < ratio; i++) bases.push_back(bases.back() * 100);
    for (int i = 0; i * ratio < MAX; i++) {
      long long int t = 0;
      for (int j = 0; i * ratio + j < MAX && j < ratio; j++) {
        t += (long long int)(dp[0][i * ratio + j].real() + 0.5) * bases[j];
      }
      res.value.push_back(t);
    }
    long long int carry = 0;
    for (int i = 0; i < res.value.size(); i++) {
      res.value[i] += carry;
      carry = res.value[i] / 1000000;
      res.value[i] %= 1000000;
    }
    for (; carry; carry /= 1000000) res.value.push_back(carry % 1000000);
    mpi_reform(res);
    return res;
  }
  static bool mpi_abs_gt(const MPI &m0, const MPI &m1) {
    if (m0.value.size() != m1.value.size())
      return m0.value.size() < m1.value.size();
    for (int i = m0.value.size() - 1; 0 <= i; i--) {
      if (m0.value[i] != m1.value[i]) return m0.value[i] < m1.value[i];
    }
    return false;
  }
  static bool mpi_abs_sl(const MPI &m0, const MPI &m1) {
    if (m0.value.size() != m1.value.size())
      return m0.value.size() > m1.value.size();
    for (int i = m0.value.size() - 1; 0 <= i; i--) {
      if (m0.value[i] != m1.value[i]) return m0.value[i] > m1.value[i];
    }
    return false;
  }
  static bool mpi_abs_eq(const MPI &m0, const MPI &m1) {
    if (m0.value.size() != m1.value.size()) return false;
    for (int i = 0; i < m0.value.size(); i++) {
      if (m0.value[i] != m1.value[i]) return false;
    }
    return true;
  }
  MPI operator+(const MPI &mpi) const {
    bool b0 = sign, b1 = mpi.sign;
    if (!b0 && !b1) return mpi_abs_add(*this, mpi);
    if (!b0 && b1) return mpi_abs_sub(*this, mpi);
    if (b0 && !b1) return mpi_abs_sub(mpi, *this);
    MPI res = mpi_abs_add(*this, mpi);
    res.sign = !res.sign;
    return res;
  }
  MPI operator-(const MPI &mpi) const {
    bool b0 = sign, b1 = mpi.sign;
    if (!b0 && !b1) return mpi_abs_sub(*this, mpi);
    if (!b0 && b1) return mpi_abs_add(*this, mpi);
    if (b0 && b1) return mpi_abs_sub(mpi, *this);
    MPI res = mpi_abs_add(*this, mpi);
    res.sign = !res.sign;
    return res;
  }
  inline MPI operator*(const MPI &mpi) const {
    MPI res = mpi_abs_mul(*this, mpi);
    if (sign != mpi.sign) res.sign = !res.sign;
    return res;
  }
  inline MPI operator/(const MPI &mpi) const {
    MPI res = mpi_abs_div(*this, mpi, true);
    if (sign != mpi.sign) res.sign = !res.sign;
    return res;
  }
  inline MPI operator%(const MPI &mpi) const {
    MPI res = mpi_abs_div(*this, mpi, false);
    if (sign) res.sign = !res.sign;
    return res;
  }
  bool operator<(const MPI &mpi) const {
    if (value.size() == 1 && value[0] == 0 && mpi.value.size() == 1 &&
        mpi.value[0] == 0)
      return false;
    bool b0 = sign, b1 = mpi.sign;
    if (!b0 && b1) return false;
    if (b0 && !b1) return true;
    if (!b0 && !b1) return mpi_abs_gt(*this, mpi);
    if (b0 && b1) return mpi_abs_sl(*this, mpi);
  }
  bool operator>(const MPI &mpi) const {
    if (value.size() == 1 && value[0] == 0 && mpi.value.size() == 1 &&
        mpi.value[0] == 0)
      return false;
    bool b0 = sign, b1 = mpi.sign;
    if (!b0 && b1) return true;
    if (b0 && !b1) return false;
    if (!b0 && !b1) return mpi_abs_sl(*this, mpi);
    if (b0 && b1) return mpi_abs_gt(*this, mpi);
  }
  inline bool operator==(const MPI &mpi) const {
    if (value.size() == 1 && value[0] == 0 && mpi.value.size() == 1 &&
        mpi.value[0] == 0)
      return true;
    if (sign != mpi.sign) return false;
    return mpi_abs_eq(*this, mpi);
  }
  inline bool operator>=(const MPI &mpi) const { return !(*this < mpi); }
  inline bool operator<=(const MPI &mpi) const { return !(*this > mpi); }
  inline bool operator!=(const MPI &mpi) const { return !(*this == mpi); }
  inline void operator+=(const MPI &mpi) { *this = *this + mpi; }
  inline void operator-=(const MPI &mpi) { *this = *this - mpi; }
  inline void operator*=(const MPI &mpi) { *this = *this * mpi; }
  inline void operator/=(const MPI &mpi) { *this = *this / mpi; }
  inline void operator%=(const MPI &mpi) { *this = *this % mpi; }
  inline friend bool operator>(long long int l, const MPI &mpi) {
    return MPI(l) > mpi;
  }
  inline friend bool operator<(long long int l, const MPI &mpi) {
    return MPI(l) < mpi;
  }
  inline friend bool operator>=(long long int l, const MPI &mpi) {
    return MPI(l) >= mpi;
  }
  inline friend bool operator<=(long long int l, const MPI &mpi) {
    return MPI(l) <= mpi;
  }
  inline friend bool operator!=(long long int l, const MPI &mpi) {
    return MPI(l) != mpi;
  }
  inline friend bool operator==(long long int l, const MPI &mpi) {
    return MPI(l) == mpi;
  }
  inline MPI operator--() {
    *this = *this - MPI(1);
    return *this;
  }
  inline MPI operator++() {
    *this = *this + MPI(1);
    return *this;
  }
  inline MPI operator++(int i) {
    MPI res = *this;
    *this = *this + MPI(1);
    return res;
  }
  inline MPI operator--(int i) {
    MPI res = *this;
    *this = *this + MPI(1);
    return res;
  }
  inline MPI operator-() {
    MPI res = *this;
    res.sign = !res.sign;
    return res;
  }
  inline friend std::ostream &operator<<(std::ostream &os, const MPI &mpi) {
    os << mpi.to_string();
    return os;
  }
  inline friend std::istream &operator>>(std::istream &is, MPI &mpi) {
    string str;
    is >> str;
    mpi = MPI(str);
    return is;
  }

 private:
  static void mpi_add_mul_reform_vec(vector<long long int> &vec) {
    long long int carry = 0;
    for (int i = 0; i < vec.size(); i++) {
      vec[i] += carry;
      carry = vec[i] / 1000000;
      vec[i] %= 1000000;
    }
    for (; carry; carry /= 1000000) vec.push_back(carry % 1000000);
    mpi_reform_vec(vec);
  }
  inline static void mpi_add_mul_reform(MPI &mpi) {
    mpi_add_mul_reform_vec(mpi.value);
  }
  static void mpi_reform_vec(vector<long long int> &vec) {
    if (vec.size() == 0) vec.push_back(0);
    while (1 < vec.size() && vec.back() == 0) vec.pop_back();
  }
  inline static void mpi_reform(MPI &mpi) { mpi_reform_vec(mpi.value); }
};
complex<double> MPI::ca[(1 << 20)];
complex<double> MPI::cb[(1 << 20)];
complex<double> MPI::omega[(1 << 20)];
complex<double> MPI::dp[2][(1 << 20)];
complex<double> MPI::dat[(1 << 20)];
long long int MPI::p10[6 + 1] = {1, 10, 100, 1000, 10000, 100000, 1000000};
long long int MPI::ratio = 6 / 2;
class IRN {
 public:
  MPI IRN_DEN;
  MPI IRN_NUM;
  bool IRN_SIGN;
  IRN() {
    IRN_DEN = 0;
    IRN_NUM = 1;
    IRN_SIGN = false;
  }
  IRN(string irn_str0, string irn_str1) {
    IRN_DEN = irn_str0;
    IRN_NUM = irn_str1;
    IRN_SIGN = false;
    if (IRN_DEN < 0) IRN_SIGN = !IRN_SIGN;
    if (IRN_NUM < 0) IRN_SIGN = !IRN_SIGN;
    IRN_DEN.sign = false;
    IRN_NUM.sign = false;
    irn_reduct(*this);
  }
  IRN(long long int irn_li0, long long int irn_li1) {
    IRN_DEN = irn_li0;
    IRN_NUM = irn_li1;
    IRN_SIGN = false;
    if (IRN_DEN < 0) IRN_SIGN = !IRN_SIGN;
    if (IRN_NUM < 0) IRN_SIGN = !IRN_SIGN;
    IRN_DEN.sign = false;
    IRN_NUM.sign = false;
    irn_reduct(*this);
  }
  IRN(long long int irn_li) {
    IRN_DEN = irn_li;
    IRN_NUM = 1;
    IRN_SIGN = false;
  }
  IRN(string irn_str) {
    IRN_DEN = irn_str;
    IRN_NUM = 1;
    IRN_SIGN = false;
  }
  IRN(MPI mpi0, MPI mpi1) {
    IRN_DEN = mpi0;
    IRN_NUM = mpi1;
    IRN_SIGN = false;
  }
  string to_string() const {
    if (IRN_SIGN && IRN_DEN != 0)
      return "-" + IRN_DEN.to_string() + "/" + IRN_NUM.to_string();
    return IRN_DEN.to_string() + "/" + IRN_NUM.to_string();
  }
  static MPI irn_mpi_gcd(MPI mpi0, MPI mpi1) {
    if (mpi1 == 0) return 1;
    if (mpi0 % mpi1 == 0) return mpi1;
    return irn_mpi_gcd(mpi1, mpi0 % mpi1);
  }
  void irn_reduct(IRN &irn_var, bool only_sign = false) const {
    if (irn_var.IRN_DEN == 0) {
      irn_var.IRN_NUM = 1;
      irn_var.IRN_SIGN = false;
      return;
    }
    if (irn_var.IRN_DEN < 0) irn_var.IRN_SIGN = !irn_var.IRN_SIGN;
    if (irn_var.IRN_NUM < 0) irn_var.IRN_SIGN = !irn_var.IRN_SIGN;
    irn_var.IRN_DEN.sign = false;
    irn_var.IRN_NUM.sign = false;
    if (only_sign) return;
    MPI irn_t = irn_mpi_gcd(irn_var.IRN_NUM, irn_var.IRN_DEN);
    irn_var.IRN_NUM /= irn_t;
    irn_var.IRN_DEN /= irn_t;
  }
  IRN irn_mul(const IRN &irn0, const IRN &irn1) const {
    IRN irn_res(1, 1);
    MPI irn_t = irn_mpi_gcd(irn0.IRN_DEN, irn1.IRN_NUM);
    irn_res.IRN_DEN = irn0.IRN_DEN / irn_t;
    irn_res.IRN_NUM = irn1.IRN_NUM / irn_t;
    irn_t = irn_mpi_gcd(irn0.IRN_NUM, irn1.IRN_DEN);
    irn_res.IRN_DEN *= irn1.IRN_DEN / irn_t;
    irn_res.IRN_NUM *= irn0.IRN_NUM / irn_t;
    if (irn1.IRN_SIGN) irn_res.IRN_SIGN = !irn_res.IRN_SIGN;
    if (irn0.IRN_SIGN) irn_res.IRN_SIGN = !irn_res.IRN_SIGN;
    if (irn_res.IRN_DEN == 0) {
      irn_res.IRN_NUM = 1;
      irn_res.IRN_SIGN = false;
    }
    return irn_res;
  }
  IRN irn_div(const IRN &irn0, const IRN &irn1) const {
    IRN irn_res(1, 1);
    MPI irn_t = irn_mpi_gcd(irn0.IRN_DEN, irn1.IRN_DEN);
    irn_res.IRN_DEN = irn0.IRN_DEN / irn_t;
    irn_res.IRN_NUM = irn1.IRN_DEN / irn_t;
    irn_t = irn_mpi_gcd(irn0.IRN_NUM, irn1.IRN_NUM);
    irn_res.IRN_DEN *= irn1.IRN_NUM / irn_t;
    irn_res.IRN_NUM *= irn0.IRN_NUM / irn_t;
    if (irn1.IRN_SIGN) irn_res.IRN_SIGN = !irn_res.IRN_SIGN;
    if (irn0.IRN_SIGN) irn_res.IRN_SIGN = !irn_res.IRN_SIGN;
    if (irn_res.IRN_DEN == 0) {
      irn_res.IRN_NUM = 1;
      irn_res.IRN_SIGN = false;
    }
    return irn_res;
  }
  IRN irn_abs_add(const IRN &irn0, const IRN &irn1) const {
    IRN irn_res(0);
    if (irn0.IRN_NUM == irn1.IRN_NUM) {
      irn_res.IRN_DEN = irn0.IRN_DEN + irn1.IRN_DEN;
      irn_res.IRN_NUM = irn0.IRN_NUM;
    } else {
      irn_res.IRN_NUM = irn0.IRN_NUM * irn1.IRN_NUM;
      irn_res.IRN_DEN = irn0.IRN_DEN * irn1.IRN_NUM;
      irn_res.IRN_DEN += irn1.IRN_DEN * irn0.IRN_NUM;
    }
    irn_reduct(irn_res, irn0.IRN_NUM == 1 || irn1.IRN_NUM == 1);
    return irn_res;
  }
  IRN irn_abs_sub(const IRN &irn0, const IRN &irn1) const {
    IRN irn_res(0);
    if (irn0.IRN_NUM == irn1.IRN_NUM) {
      irn_res.IRN_DEN = irn0.IRN_DEN - irn1.IRN_DEN;
      irn_res.IRN_NUM = irn0.IRN_NUM;
    } else {
      irn_res.IRN_NUM = irn0.IRN_NUM * irn1.IRN_NUM;
      irn_res.IRN_DEN = irn0.IRN_DEN * irn1.IRN_NUM;
      irn_res.IRN_DEN -= irn1.IRN_DEN * irn0.IRN_NUM;
    }
    irn_reduct(irn_res, irn0.IRN_NUM == 0 || irn1.IRN_NUM == 0);
    return irn_res;
  }
  IRN irn_add(const IRN &irn0, const IRN &irn1) const {
    if (irn0.IRN_SIGN && irn1.IRN_SIGN) {
      IRN irn_res = irn_abs_add(irn0, irn1);
      irn_res.IRN_SIGN = !irn_res.IRN_SIGN;
      return irn_res;
    }
    if (!irn0.IRN_SIGN && !irn1.IRN_SIGN) return irn_abs_add(irn0, irn1);
    IRN irn_res;
    if (!irn0.IRN_SIGN && irn1.IRN_SIGN) irn_res = irn_abs_sub(irn0, irn1);
    if (irn0.IRN_SIGN && !irn1.IRN_SIGN) irn_res = irn_abs_sub(irn1, irn0);
    if (irn_res.IRN_DEN < 0) {
      irn_res.IRN_DEN.sign = false;
      irn_res.IRN_SIGN = true;
    }
    return irn_res;
  }
  IRN irn_sub(const IRN &irn0, const IRN &irn1) const {
    if (!irn0.IRN_SIGN && irn1.IRN_SIGN) return irn_abs_add(irn0, irn1);
    if (irn0.IRN_SIGN && !irn1.IRN_SIGN) {
      IRN irn_res = irn_abs_add(irn0, irn1);
      irn_res.IRN_SIGN = !irn_res.IRN_SIGN;
      return irn_res;
    }
    IRN irn_res;
    if (irn0.IRN_SIGN && irn1.IRN_SIGN) {
      irn_res = irn_abs_sub(irn0, irn1);
      irn_res.IRN_SIGN = !irn_res.IRN_SIGN;
    }
    if (!irn0.IRN_SIGN && !irn1.IRN_SIGN) {
      irn_res = irn_abs_sub(irn0, irn1);
    }
    if (irn_res.IRN_DEN < 0) {
      irn_res.IRN_DEN.sign = false;
      irn_res.IRN_SIGN = true;
    }
    return irn_res;
  }
  bool operator<(const IRN &irn_var) const {
    if (this->IRN_DEN == 0 && irn_var.IRN_DEN == 0) return false;
    bool b0 = this->IRN_SIGN, b1 = irn_var.IRN_SIGN;
    if (b0 && !b1) return true;
    if (!b1 && b0) return false;
    MPI left = this->IRN_DEN * irn_var.IRN_NUM;
    MPI right = irn_var.IRN_DEN * this->IRN_NUM;
    if (!b0 && !b1) return left < right;
    return right < left;
  }
  bool operator>(const IRN &irn_var) const {
    if (this->IRN_DEN == 0 && irn_var.IRN_DEN == 0) return false;
    bool b0 = this->IRN_SIGN, b1 = irn_var.IRN_SIGN;
    if (b0 && !b1) return false;
    if (!b0 && b1) return true;
    MPI left = this->IRN_DEN * irn_var.IRN_NUM;
    MPI right = irn_var.IRN_DEN * this->IRN_NUM;
    if (!b0 && !b1) return left > right;
    return right < left;
  }
  bool operator==(const IRN &irn_var) const {
    if (this->IRN_DEN == 0 && irn_var.IRN_DEN == 0) return true;
    if (this->IRN_SIGN && !irn_var.IRN_SIGN) return false;
    if (!this->IRN_SIGN && irn_var.IRN_SIGN) return false;
    return this->IRN_DEN == irn_var.IRN_DEN && this->IRN_NUM == irn_var.IRN_NUM;
  }
  IRN operator+(const IRN &irn_var) const { return irn_add(*this, irn_var); }
  IRN operator-(const IRN &irn_var) const { return irn_sub(*this, irn_var); }
  IRN operator/(const IRN &irn_var) const { return irn_div(*this, irn_var); }
  IRN operator*(const IRN &irn_var) const { return irn_mul(*this, irn_var); }
  void operator+=(const IRN &irn_var) { *this = *this + irn_var; }
  void operator-=(const IRN &irn_var) { *this = *this - irn_var; }
  void operator*=(const IRN &irn_var) { *this = *this * irn_var; }
  void operator/=(const IRN &irn_var) { *this = *this / irn_var; }
  IRN operator<=(const IRN &irn_var) const { return !(irn_var < *this); }
  IRN operator>=(const IRN &irn_var) const { return !(*this < irn_var); }
  IRN operator!=(const IRN &irn_var) const { return !(*this == irn_var); }
  friend std::ostream &operator<<(std::ostream &os, const IRN &irn_var) {
    os << irn_var.to_string();
    return os;
  }

 private:
};
MPI N = 2;
long long int n;
IRN recur(long long int m, int cnt = 0) {
  if (m == 0)
    while (true)
      ;
  if (m == 1) return 0;
  N *= 2;
  m *= 2;
  if (m < n)
    return IRN(1, 1) + recur(m, cnt + 1);
  else
    return IRN(1, 1) + IRN(m - n, m) * recur(m - n, cnt + 1);
}
int main() {
  cin >> n;
  long long int shift = 0;
  for (; n % 2 == 0; n /= 2) shift++;
  if (n == 1) {
    cout << shift << "/1" << endl;
    return 0;
  }
  IRN res = IRN(1, 1) + recur(2);
  res *= IRN(N, N - 1);
  res += shift;
  cout << res << endl;
}

```