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 long long mod = 1e9 + 7;
const long double eps = 1e-9;
const int inf = (1 << 30);
const long long INF = (1LL << 61);
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
long long expo(long long x, long long y) {
  long long res = 1;
  x = x % mod;
  while (y > 0) {
    if (y & 1) res = (res * x) % mod;
    y = y >> 1;
    x = (x * x) % mod;
  }
  return res;
}
void matmul(long long a[][2], long long b[][2]) {
  long long tmp[2][2];
  for (int i = 0; i < 2; i++) {
    for (int j = 0; j < 2; j++) {
      tmp[i][j] = 0;
      for (int k = 0; k < 2; k++)
        tmp[i][j] = (tmp[i][j] + a[i][k] * b[k][j]) % mod;
    }
  }
  for (int i = 0; i < 2; i++)
    for (int j = 0; j < 2; j++) a[i][j] = tmp[i][j];
}
long long fibo(int n) {
  if (n == 0)
    return 0;
  else if (n == 1)
    return 1;
  long long T[2][2] = {{0, 1}, {1, 1}};
  long long res[2][2] = {{1, 0}, {0, 1}};
  n--;
  while (n) {
    if (n & 1) matmul(res, T);
    n >>= 1;
    matmul(T, T);
  }
  return res[1][1];
}
map<long long, string> m;
vector<pair<long long, string> > v;
string better(string x, string y) {
  if (x.size() < y.size())
    return x;
  else
    return y;
}
void brute() {
  for (long long i = 2; i <= 1e5; i++) {
    int p = 1;
    string s, t;
    for (long long j = i; j <= 1e10; j = j * i, p++) {
      s = (to_string(i) + "^" + to_string(p));
      if (m.find(j) != m.end())
        t = m[j];
      else
        t = to_string(j);
      m[j] = better(s, t);
    }
  }
  for (auto it : m) v.push_back(it);
}
string need(long long x) {
  if (x == 0)
    return "";
  else if (m.count(x))
    return ("+" + m[x]);
  else
    return ("+" + to_string(x));
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  long long n;
  cin >> n;
  brute();
  string ans = to_string(n);
  int sz = v.size();
  int ind = sz - 1;
  for (int i = 0; i < sz; i++) {
    bool yes = 0;
    string tmp;
    if (v[i].first <= n) {
      tmp = v[i].second + need(n - v[i].first);
      ans = better(ans, tmp);
    }
    while (ind >= 0) {
      if (v[i].first * v[ind].first <= n) {
        yes = 1;
        break;
      }
      ind--;
    }
    if (yes) {
      tmp = v[i].second + "*" + v[ind].second;
      long long x = n - (v[i].first * v[ind].first);
      tmp += need(x);
      ans = better(ans, tmp);
    }
    int j = ind - 1, c = 0;
    while (j >= 0 && v[i].first * v[j].first <= n) {
      tmp = v[i].second + "*" + v[j].second;
      long long x = n - (v[i].first * v[j].first);
      tmp += need(x);
      ans = better(ans, tmp);
      j--;
      if (c >= 10) break;
      c++;
    }
  }
  cout << ans;
  return 0;
}
