Vasya is a regular participant at programming contests and is already experienced in finding important sentences in long statements. Of course, numbers constraints are important — factorization of a number less than 1000000 is easier than of a number less than 1000000000. However, sometimes it's hard to understand the number at the first glance. Could it be shortened? For example, instead of 1000000 you could write 10^{6}, instead of 1000000000 —10^{9}, instead of 1000000007 — 10^{9}+7.

Vasya decided that, to be concise, the notation should follow several rules: 

  * the notation should only consist of numbers, operations of addition ("+"), multiplication ("*") and exponentiation ("^"), in particular, the use of braces is forbidden; 
  * the use of several exponentiation operations in a row is forbidden, for example, writing "2^3^4" is unacceptable; 
  * the value of the resulting expression equals to the initial number; 
  * the notation should consist of the minimal amount of symbols. 



Given n, find the equivalent concise notation for it.

Input

The only line contains a single integer n (1 ≤ n ≤ 10 000 000 000).

Output

Output a concise notation of the number n. If there are several concise notations, output any of them.

Examples

Input

2018


Output

2018


Input

1000000007


Output

10^9+7


Input

10000000000


Output

100^5


Input

2000000000


Output

2*10^9

Note

The third sample allows the answer 10^10 also of the length 5.
#include <bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
using namespace std;
template <class T1, class T2>
inline bool chmax(T1 &a, T2 b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <class T1, class T2>
inline bool chmin(T1 &a, T2 b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
const double EPS = 1e-9, PI = acos(-1);
const double pi = 3.141592653589793238462643383279;
template <int mod>
struct ModInt {
  int x;
  ModInt() : x(0) {}
  ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}
  ModInt &operator+=(const ModInt &p) {
    if ((x += p.x) >= mod) x -= mod;
    return *this;
  }
  ModInt &operator-=(const ModInt &p) {
    if ((x += mod - p.x) >= mod) x -= mod;
    return *this;
  }
  ModInt &operator*=(const ModInt &p) {
    x = (int)(1LL * x * p.x % mod);
    return *this;
  }
  ModInt &operator/=(const ModInt &p) {
    *this *= p.inverse();
    return *this;
  }
  ModInt operator-() const { return ModInt(-x); }
  ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }
  ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }
  ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }
  ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }
  bool operator==(const ModInt &p) const { return x == p.x; }
  bool operator!=(const ModInt &p) const { return x != p.x; }
  ModInt inverse() const {
    int a = x, b = mod, u = 1, v = 0, t;
    while (b > 0) {
      t = a / b;
      swap(a -= t * b, b);
      swap(u -= t * v, v);
    }
    return ModInt(u);
  }
  ModInt pow(int64_t n) const {
    ModInt ret(1), mul(x);
    while (n > 0) {
      if (n & 1) ret *= mul;
      mul *= mul;
      n >>= 1;
    }
    return ret;
  }
  friend ostream &operator<<(ostream &os, const ModInt &p) { return os << p.x; }
  friend istream &operator>>(istream &is, ModInt &a) {
    int64_t t;
    is >> t;
    a = ModInt<mod>(t);
    return (is);
  }
  static int get_mod() { return mod; }
};
using modint = ModInt<1000000000>;
template <typename T>
struct Combination {
  vector<T> _fact, _rfact, _inv;
  Combination(int sz) : _fact(sz + 1), _rfact(sz + 1), _inv(sz + 1) {
    _fact[0] = _rfact[sz] = _inv[0] = 1;
    for (int i = 1; i <= sz; i++) _fact[i] = _fact[i - 1] * i;
    _rfact[sz] /= _fact[sz];
    for (int i = sz - 1; i >= 0; i--) _rfact[i] = _rfact[i + 1] * (i + 1);
    for (int i = 1; i <= sz; i++) _inv[i] = _rfact[i] * _fact[i - 1];
  }
  inline T fact(int k) const { return _fact[k]; }
  inline T rfact(int k) const { return _rfact[k]; }
  inline T inv(int k) const { return _inv[k]; }
  T P(int n, int r) const {
    if (r < 0 || n < r) return 0;
    return fact(n) * rfact(n - r);
  }
  T C(int p, int q) const {
    if (q < 0 || p < q) return 0;
    return fact(p) * rfact(q) * rfact(p - q);
  }
  T H(int n, int r) const {
    if (n < 0 || r < 0) return (0);
    return r == 0 ? 1 : C(n + r - 1, r);
  }
};
long long GCD(long long a, long long b) { return (b == 0) ? a : GCD(b, a % b); }
long long LCM(long long a, long long b) { return a / GCD(a, b) * b; }
map<long long, string> mp;
string f(long long n) {
  if (mp.find(n) != mp.end()) {
    return mp[n];
  }
  string ans = to_string(n);
  int mi = to_string(n).size();
  for (long long i = 2; i * i * i <= n; i++) {
    long long t = i;
    long long c = 1;
    while (t <= n) {
      long long p = n / t;
      long long q = n - p * t;
      int len = 0;
      if (p == 1) {
        if (c == 1) {
          len += to_string(i).size();
          if (q == 0) {
            if (mi > len) {
              mi = len;
              ans = to_string(i);
            }
          } else {
            len++;
            len += to_string(q).size();
            if (mi > len) {
              mi = len;
              ans = to_string(i) + '+' + to_string(q);
            }
          }
        } else {
          len += to_string(i).size();
          len++;
          len += to_string(c).size();
          if (q == 0) {
            if (mi > len) {
              mi = len;
              ans = to_string(i) + '^' + to_string(c);
            }
          } else {
            len++;
            len += to_string(q).size();
            if (mi > len) {
              mi = len;
              ans = to_string(i) + '^' + to_string(c) + '+' + to_string(q);
            }
          }
        }
      } else {
        len += to_string(p).size();
        len++;
        if (c == 1) {
          len += to_string(i).size();
          if (q == 0) {
            if (mi > len) {
              mi = len;
              ans = to_string(p) + '*' + to_string(i);
            }
          } else {
            len++;
            len += to_string(q).size();
            if (mi > len) {
              mi = len;
              ans = to_string(p) + '*' + to_string(i) + '+' + to_string(q);
            }
          }
        } else {
          len += to_string(i).size();
          len++;
          len += to_string(c).size();
          if (q == 0) {
            if (mi > len) {
              mi = len;
              ans = to_string(p) + '*' + to_string(i) + '^' + to_string(c);
            }
          } else {
            len++;
            len += to_string(q).size();
            if (mi > len) {
              mi = len;
              ans = to_string(p) + '*' + to_string(i) + '^' + to_string(c) +
                    '+' + to_string(q);
            }
          }
        }
      }
      t *= i;
      c++;
    }
  }
  return mp[n] = ans;
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  long long n;
  cin >> n;
  map<long long, string> mpp;
  for (long long i = 2; i * i <= n; i++) {
    long long t = i;
    long long c = 1;
    while (t <= n) {
      int len = to_string(i).size() + 1 + to_string(c).size();
      if (len < to_string(t).size()) {
        if (mp.find(t) == mp.end()) {
          string s = to_string(i) + '^' + to_string(c);
          mp[t] = s;
          mpp[t] = s;
        } else if (mp[t].size() > len) {
          string s = to_string(i) + '^' + to_string(c);
          mp[t] = s;
          mpp[t] = s;
        }
      }
      t *= i;
      c++;
    }
  }
  if (n <= 9) {
    cout << n << endl;
  } else {
    string ans = "";
    int mi = 0;
    if (mp.find(n) != mp.end()) {
      ans = mp[n];
    } else {
      ans = to_string(n);
    }
    mi = ans.size();
    for (long long i = 2; i * i * i * i <= n; i++) {
      long long t = i;
      long long c = 1;
      while (t <= n) {
        long long p = n / t;
        long long q = n - p * t;
        string res = f(q);
        string res2 = f(p);
        bool fg = true;
        bool fg2 = true;
        if (res == to_string(q)) fg = false;
        if (mpp.find(p) == mpp.end() || res2 == to_string(p)) fg2 = false;
        int len = 0;
        if (p == 1) {
          if (c == 1) {
            len += to_string(i).size();
            if (q == 0) {
              if (mi > len) {
                mi = len;
                ans = to_string(i);
              }
            } else {
              len++;
              if (!fg) {
                len += to_string(q).size();
                if (mi > len) {
                  mi = len;
                  ans = to_string(i) + '+' + to_string(q);
                }
              } else {
                len += res.size();
                if (mi > len) {
                  mi = len;
                  ans = to_string(i) + '+' + res;
                }
              }
            }
          } else {
            len += to_string(i).size();
            len++;
            len += to_string(c).size();
            if (q == 0) {
              if (mi > len) {
                mi = len;
                ans = to_string(i) + '^' + to_string(c);
              }
            } else {
              len++;
              if (!fg) {
                len += to_string(q).size();
                if (mi > len) {
                  mi = len;
                  ans = to_string(i) + '^' + to_string(c) + '+' + to_string(q);
                }
              } else {
                len += res.size();
                if (mi > len) {
                  mi = len;
                  ans = to_string(i) + '^' + to_string(c) + '+' + res;
                }
              }
            }
          }
        } else {
          if (!fg2) {
            len += to_string(p).size();
            len++;
            if (c == 1) {
              len += to_string(i).size();
              if (q == 0) {
                if (mi > len) {
                  mi = len;
                  ans = to_string(p) + '*' + to_string(i);
                }
              } else {
                len++;
                if (!fg) {
                  len += to_string(q).size();
                  if (mi > len) {
                    mi = len;
                    ans =
                        to_string(p) + '*' + to_string(i) + '+' + to_string(q);
                  }
                } else {
                  len += res.size();
                  if (mi > len) {
                    mi = len;
                    ans = to_string(p) + '*' + to_string(i) + '+' + res;
                  }
                }
              }
            } else {
              len += to_string(i).size();
              len++;
              len += to_string(c).size();
              if (q == 0) {
                if (mi > len) {
                  mi = len;
                  ans = to_string(p) + '*' + to_string(i) + '^' + to_string(c);
                }
              } else {
                len++;
                if (!fg) {
                  len += to_string(q).size();
                  if (mi > len) {
                    mi = len;
                    ans = to_string(p) + '*' + to_string(i) + '^' +
                          to_string(c) + '+' + to_string(q);
                  }
                } else {
                  len += res.size();
                  if (mi > len) {
                    mi = len;
                    ans = to_string(p) + '*' + to_string(i) + '^' +
                          to_string(c) + '+' + res;
                  }
                }
              }
            }
          } else {
            len += res2.size();
            len++;
            if (c == 1) {
              len += to_string(i).size();
              if (q == 0) {
                if (mi > len) {
                  mi = len;
                  ans = res2 + '*' + to_string(i);
                }
              } else {
                len++;
                if (!fg) {
                  len += to_string(q).size();
                  if (mi > len) {
                    mi = len;
                    ans = res2 + '*' + to_string(i) + '+' + to_string(q);
                  }
                } else {
                  len += res.size();
                  if (mi > len) {
                    mi = len;
                    ans = res2 + '*' + to_string(i) + '+' + res;
                  }
                }
              }
            } else {
              len += to_string(i).size();
              len++;
              len += to_string(c).size();
              if (q == 0) {
                if (mi > len) {
                  mi = len;
                  ans = res2 + '*' + to_string(i) + '^' + to_string(c);
                }
              } else {
                len++;
                if (!fg) {
                  len += to_string(q).size();
                  if (mi > len) {
                    mi = len;
                    ans = res2 + '*' + to_string(i) + '^' + to_string(c) + '+' +
                          to_string(q);
                  }
                } else {
                  len += res.size();
                  if (mi > len) {
                    mi = len;
                    ans = res2 + '*' + to_string(i) + '^' + to_string(c) + '+' +
                          res;
                  }
                }
              }
            }
          }
        }
        c++;
        t *= i;
      }
    }
    cout << ans << endl;
  }
  return 0;
}
