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 N = 100010;
unordered_map<long long, string> mp, mp34;
int len(long long n) {
  int ans = 0;
  while (n) {
    ans++;
    n /= 10;
  }
  return ans;
}
char s[25];
string tostring(long long n) {
  int tmp = 0;
  while (n) {
    s[tmp++] = n % 10 + '0';
    n /= 10;
  }
  for (int i = 0; 2 * i < tmp; i++) swap(s[i], s[tmp - i - 1]);
  s[tmp] = 0;
  string ans = s;
  return ans;
}
int main() {
  long long n;
  cin >> n;
  if (n == 10000000000LL) {
    cout << "10^10" << endl;
    return 0;
  }
  string ans = tostring(n);
  for (long long a = 1; a < 100; a++) {
    int l = len(a) + 1;
    if (a == 1) l = 0;
    for (long long b = 2; a * b * b <= n && l + 2 + len(b) < ans.length();
         b++) {
      long long x = a * b * b, cnt = 2;
      while (x <= n) {
        string tmp;
        if (a > 1) tmp = tostring(a) + "*";
        tmp += tostring(b) + "^" + tostring(cnt);
        if (tmp.length() >= ans.length()) break;
        if (tmp.length() <= 4 &&
            (!mp34.count(x) || mp34[x].length() > tmp.length()))
          mp34[x] = tmp;
        if (!mp.count(x) || mp[x].length() > tmp.length()) mp[x] = tmp;
        long long y = n - x;
        string yy = tostring(y);
        if (y) tmp += "+" + yy;
        if (tmp.length() < ans.length()) ans = tmp;
        x *= b;
        cnt++;
      }
    }
  }
  for (long long a = 2; a < 1000; a++) {
    for (unordered_map<long long, string>::iterator it = mp34.begin();
         it != mp34.end(); it++) {
      if (a * it->first > n) continue;
      long long x = a * it->first;
      long long y = n - a * it->first;
      if (!y || y >= 10) continue;
      string tmp = tostring(a) + "*" + it->second + "+" + tostring(y);
      if (tmp.length() < ans.length()) ans = tmp;
    }
  }
  for (unordered_map<long long, string>::iterator it = mp.begin();
       it != mp.end(); it++) {
    if (it->second.length() > 5) continue;
    if (mp34.count(n - it->first)) {
      string tmp = it->second + "+" + mp34[n - it->first];
      if (tmp.length() < ans.length()) ans = tmp;
    }
    if (n - it->first == 0) continue;
    long long x = n - it->first;
    if (mp34.count(x)) {
      string tmp = it->second + "*" + mp34[x];
      if (tmp.length() < ans.length()) ans = tmp;
    }
    if (n % (n - it->first)) continue;
    x = n / (n - it->first);
    if (mp34.count(x)) {
      string tmp = it->second + "*" + mp34[x];
      if (tmp.length() < ans.length()) ans = tmp;
    }
  }
  for (unordered_map<long long, string>::iterator it = mp34.begin();
       it != mp34.end(); it++) {
    for (unordered_map<long long, string>::iterator it2 = mp34.begin();
         it2 != mp34.end(); it2++) {
      if (it->second.length() + it2->second.length() + 1 >= ans.length())
        continue;
      if (it->first <= n / it2->first) {
        long long x = it->first * it2->first;
        string tmp = it->second + "*" + it2->second;
        if (n != x) tmp += "+" + tostring(n - x);
        if (tmp.length() < ans.length()) ans = tmp;
      }
      if (it->first + it2->first <= n) {
        long long x = it->first + it2->first;
        string tmp = it->second + "+" + it2->second;
        if (n != x) tmp += "+" + tostring(n - x);
        if (tmp.length() < ans.length()) ans = tmp;
      }
    }
  }
  for (unordered_map<long long, string>::iterator it = mp34.begin();
       it != mp34.end(); it++) {
    if (n % it->first) continue;
    string tmp = tostring(n / it->first) + "*" + it->second;
    if (tmp.length() < ans.length()) ans = tmp;
  }
  cout << ans << endl;
  return 0;
}
