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>
using namespace std;
const int infinity = 2000000999 / 2;
const long long int inff = 4000000000000000999;
template <class T>
T get() {
  T a;
  cin >> a;
  return a;
}
template <class T, class U>
ostream& operator<<(ostream& out, const pair<T, U>& par) {
  out << "[" << par.first << ";" << par.second << "]";
  return out;
}
template <class T>
ostream& operator<<(ostream& out, const set<T>& cont) {
  out << "{";
  for (const auto& x : cont) out << x << ", ";
  out << "}";
  return out;
}
template <class T, class U>
ostream& operator<<(ostream& out, const map<T, U>& cont) {
  out << "{";
  for (const auto& x : cont) out << x << ", ";
  out << "}";
  return out;
}
template <class T>
ostream& operator<<(ostream& out, const vector<T>& v) {
  for (int i = 0; i < (int)v.size(); i++) {
    if (i) out << " ";
    out << v[i];
  }
  out << endl;
  return out;
}
bool ccw(complex<long double> p, complex<long double> a,
         complex<long double> b) {
  if ((conj(a - p) * (b - p)).imag() <= 0)
    return (0);
  else
    return (1);
}
int main() {
  cin.sync_with_stdio(false);
  cout.sync_with_stdio(false);
  long long int n = get<long long int>();
  string s = to_string(n);
  int m = s.size();
  int mini = m;
  string minis = s;
  vector<vector<long long int> > exp(1, vector<long long int>(1, 1));
  map<long long int, pair<long long int, long long int> > E;
  for (long long int a = 2; a * a <= n; a++) {
    exp.push_back(vector<long long int>(0));
    long long int last = 1;
    exp[a - 1].push_back(last);
    long long int pw = 0;
    while (last < n) {
      last = last * a;
      if (last > n) break;
      pw++;
      exp[a - 1].push_back(last);
      if (pw > 1) {
        if (E.find(last) == E.end())
          E[last] = {a, pw};
        else {
          if ((to_string(a) + to_string(pw)).size() <
              (to_string(E[last].first) + to_string(E[last].second)).size())
            E[last] = {a, pw};
        }
      }
    }
  }
  if (0) cout << "E: " << E << endl;
  for (auto& ex : E) {
    if (ex.first > n) break;
    if (ex.first == n) {
      if ((to_string(ex.second.first) + to_string(ex.second.second)).size() +
              1 <
          mini) {
        minis = to_string(ex.second.first) + "^" + to_string(ex.second.second);
        mini = minis.size();
      }
    } else {
      long long int rem = n - ex.first;
      if ((to_string(ex.second.first) + to_string(ex.second.second) +
           to_string(rem))
                  .size() +
              2 <
          mini) {
        if (0) cout << rem << " + " << ex << " = n " << endl;
        minis = to_string(ex.second.first) + "^" + to_string(ex.second.second) +
                "+" + to_string(rem);
        mini = minis.size();
      }
      if (n % ex.first == 0) {
        long long int rem = n / ex.first;
        if ((to_string(ex.second.first) + to_string(ex.second.second) +
             to_string(rem))
                    .size() +
                2 <
            mini) {
          minis = to_string(rem) + "*" + to_string(ex.second.first) + "^" +
                  to_string(ex.second.second);
          mini = minis.size();
        }
      } else {
        long long int rem = n / ex.first;
        long long int rm = n - rem * ex.first;
        if ((to_string(ex.second.first) + to_string(rm) +
             to_string(ex.second.second) + to_string(rem))
                    .size() +
                3 <
            mini) {
          if (0) cout << " = " << rem << " * " << ex << endl;
          minis = to_string(rem) + "*" + to_string(ex.second.first) + "^" +
                  to_string(ex.second.second) + "+" + to_string(rm);
          mini = minis.size();
        }
      }
      auto it = E.upper_bound(n - ex.first);
      if (it != E.begin()) {
        it--;
        string news = to_string(ex.second.first) + "^" +
                      to_string(ex.second.second) + "+" +
                      to_string(it->second.first) + "^" +
                      to_string(it->second.second);
        if (it->first + ex.first == n) {
          if (news.size() < mini) {
            mini = news.size();
            minis = news;
          }
        } else {
          news += "+" + to_string(n - ex.first - it->first);
          if ((int)news.size() < mini) {
            mini = news.size();
            minis = news;
          }
        }
      }
    }
  }
  if (0) cout << "minis now: " << minis << endl;
  if (mini > 9) {
    for (int a = 0; a < (int)10; a++) {
      if (a < 2) continue;
      for (int b = 0; b < (int)10; b++) {
        if (b < 2) continue;
        for (int c = 0; c < (int)10; c++) {
          if (c < 2) continue;
          for (int d = 0; d < (int)10; d++) {
            if (d < 2) continue;
            for (int e = 0; e < (int)10; e++) {
              if (e < 2) continue;
              long long int cis =
                  (long long int)e * exp[a - 1][b] + exp[c - 1][d];
              if (cis == n) {
                mini = 9;
                minis = to_string(e) + "*" + to_string(a) + "^" + to_string(b) +
                        "+" + to_string(c) + "^" + to_string(d);
                break;
              }
              cis = e + exp[a - 1][b] * exp[c - 1][d];
              if (cis == n) {
                mini = 9;
                minis = to_string(e) + "+" + to_string(a) + "^" + to_string(b) +
                        "*" + to_string(c) + "^" + to_string(d);
                break;
              }
            }
          }
        }
      }
    }
  }
  cout << minis << endl;
}
