#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;
}
