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;
using namespace std;
int getLen(long long n) {
  if (n == 0) return 1;
  int ans = 0;
  while (n > 0) {
    n /= 10;
    ans++;
  }
  return ans;
}
const int MAXS = 6;
const int MAXC = MAXS + 2;
vector<int> simpleNums[MAXS];
map<long long, string> cNums[MAXC];
const int mbest = 10000;
string best[mbest];
const long long INF = 1e12;
long long ppp(long long b, int p) {
  if (b == 0) return 0;
  long long res = 1;
  for (int i = 0; i < p; ++i) {
    if (INF / b <= res) return -1;
    res *= b;
  }
  return res;
}
string join(long long l, int r, char op) {
  return to_string(l) + op + to_string(r);
}
long long root(long long n, int p) {
  long long x = pow(n + 0.0, 1.0 / p) - 0.4;
  for (int a = x - 100; a < x + 100; ++a)
    if (ppp(a, p) == n) return a;
  return -1;
}
void genSimple(int len) {
  int mx = 1;
  for (int i = 0; i < len; ++i) mx *= 10;
  for (int i = 1; i < mx; ++i) simpleNums[len].push_back(i);
}
void tryMin(string &a, string c) {
  if (a.length() > c.length()) a = c;
}
void tryMin(int len, long long v, string c) {
  if (cNums[len][v] == "") cNums[len][v] = to_string(v);
  tryMin(cNums[len][v], c);
}
void genComplex(int len) {
  for (int il = 1; il < len - 2; ++il)
    for (int jr = 1; jr < il + 1; ++jr) {
      if (jr + il < len) {
        for (auto a : cNums[il])
          for (auto b : cNums[jr]) {
            tryMin(len, a.first * b.first, a.second + "*" + b.second);
          }
        for (auto a : simpleNums[il])
          for (auto b : cNums[jr]) {
            tryMin(len, a * b.first, to_string(a) + "*" + b.second);
          }
        for (auto a : cNums[il])
          for (auto b : simpleNums[jr]) {
            tryMin(len, a.first * b, a.second + "*" + to_string(b));
          }
      }
    }
  if (len > 2)
    for (auto a : simpleNums[len - 2])
      for (int p = 2; p < 10; ++p) {
        long long res = ppp(a, p);
        if (res > 0) tryMin(len, res, join(a, p, '^'));
      }
  if (len > 3)
    for (auto a : simpleNums[len - 3])
      for (int p = 10; p < 100; ++p) {
        long long res = ppp(a, p);
        if (res > 0) tryMin(len, res, join(a, p, '^'));
      }
}
string minL(const string &a, const string &b) {
  if (a.length() < b.length()) return a;
  return b;
}
string getMin(long long n, bool useAdd, int maxLen, int sm = 2) {
  if (maxLen < 0 || n < 0) return "asdjhaksfgajshhfaskjfjksdhfjkdshghjd";
  for (int i = 0; i < MAXC; ++i) {
    if (cNums[i].count(n) != 0) return cNums[i][n];
  }
  string res = to_string(n);
  int l = getLen(n);
  maxLen = min(maxLen, l);
  if (maxLen <= MAXC) {
    return res;
  }
  for (int p = 2; p < 45; ++p) {
    long long base = root(n, p);
    if (base > 1) res = minL(res, join(base, p, '^'));
  }
  int mx = min(maxLen / 2, 4);
  if (useAdd) {
    for (auto la : simpleNums[mx]) {
      string lenL = to_string(la);
      string lenR = getMin(n - la, false, maxLen - lenL.length() - 1);
      res = minL(res, lenL + "+" + lenR);
    }
    for (auto p : cNums[mx]) {
      long long la = p.first;
      string lenL = p.second;
      string lenR = getMin(n - la, false, maxLen - lenL.length() - 1);
      res = minL(res, lenL + "+" + lenR);
    }
  }
  for (long long i = sm; i * i <= n; ++i)
    if (n % i == 0) {
      if (sm == 2) sm = 3;
      string lenL = to_string(i);
      string lenR = getMin(n / i, true, maxLen - lenL.length() - 1, sm);
      res = minL(res, lenL + "*" + lenR);
    }
  for (auto p : cNums[mx]) {
    long long la = p.first;
    string lenL = p.second;
    if (n % la == 0) {
      string lenR = getMin(n / la, false, maxLen - lenL.length() - 1);
      res = minL(res, lenL + "*" + lenR);
    }
  }
  if (res.length() <= maxLen)
    return res;
  else
    return "A LONG LONG FUCKING STRING";
}
string getMin(long long n) { return getMin(n, true, getLen(n)); }
int main() {
  ios_base::sync_with_stdio(false);
  for (int i = 1; i < MAXS; ++i) {
    genSimple(i);
  }
  for (int i = 1; i < MAXC; ++i) {
    genComplex(i);
  }
  long long n;
  cin >> n;
  cout << getMin(n) << endl;
  return 0;
}
