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 ll = long long;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;
template <typename...>
static inline int getchar_unlocked(void) {
  return getchar();
}
template <typename...>
static inline void putchar_unlocked(int c) {
  putchar(c);
}
void reader(int& x) {
  int k, m = 0;
  x = 0;
  for (;;) {
    (k) = getchar_unlocked();
    if (k == '-') {
      m = 1;
      break;
    }
    if ('0' <= k && k <= '9') {
      x = k - '0';
      break;
    }
  }
  for (;;) {
    (k) = getchar_unlocked();
    if (k < '0' || k > '9') break;
    x = x * 10 + k - '0';
  }
  if (m) x = -x;
}
void reader(ll& x) {
  int k, m = 0;
  x = 0;
  for (;;) {
    (k) = getchar_unlocked();
    if (k == '-') {
      m = 1;
      break;
    }
    if ('0' <= k && k <= '9') {
      x = k - '0';
      break;
    }
  }
  for (;;) {
    (k) = getchar_unlocked();
    if (k < '0' || k > '9') break;
    x = x * 10 + k - '0';
  }
  if (m) x = -x;
}
int reader(char c[]) {
  int i, s = 0;
  for (;;) {
    (i) = getchar_unlocked();
    if (i != ' ' && i != '\n' && i != '\r' && i != '\t' && i != EOF) break;
  }
  c[s++] = i;
  for (;;) {
    (i) = getchar_unlocked();
    if (i == ' ' || i == '\n' || i == '\r' || i == '\t' || i == EOF) break;
    c[s++] = i;
  }
  c[s] = '\0';
  return s;
}
int reader(string& c) {
  int i;
  for (;;) {
    (i) = getchar_unlocked();
    if (i != ' ' && i != '\n' && i != '\r' && i != '\t' && i != EOF) break;
  }
  c.push_back(i);
  for (;;) {
    (i) = getchar_unlocked();
    if (i == ' ' || i == '\n' || i == '\r' || i == '\t' || i == EOF) break;
    c.push_back(i);
  };
  return ((int)c.size());
}
template <class T, class S>
void reader(T& x, S& y) {
  reader(x);
  reader(y);
}
template <class T, class S, class U>
void reader(T& x, S& y, U& z) {
  reader(x);
  reader(y);
  reader(z);
}
template <class T, class S, class U, class V>
void reader(T& x, S& y, U& z, V& w) {
  reader(x);
  reader(y);
  reader(z);
  reader(w);
}
void writer(int x, char c) {
  int s = 0, m = 0;
  char f[10];
  if (x < 0) m = 1, x = -x;
  while (x) f[s++] = x % 10, x /= 10;
  if (!s) f[s++] = 0;
  if (m) putchar_unlocked('-');
  while (s--) putchar_unlocked(f[s] + '0');
  putchar_unlocked(c);
}
void writer(ll x, char c) {
  int s = 0, m = 0;
  char f[20];
  if (x < 0) m = 1, x = -x;
  while (x) f[s++] = x % 10, x /= 10;
  if (!s) f[s++] = 0;
  if (m) putchar_unlocked('-');
  while (s--) putchar_unlocked(f[s] + '0');
  putchar_unlocked(c);
}
void writer(const char c[]) {
  int i;
  for (i = 0; c[i] != '\0'; i++) putchar_unlocked(c[i]);
}
void writer(const string& x, char c) {
  int i;
  for (i = 0; x[i] != '\0'; i++) putchar_unlocked(x[i]);
  putchar_unlocked(c);
}
void writer(const char x[], char c) {
  int i;
  for (i = 0; x[i] != '\0'; i++) putchar_unlocked(x[i]);
  putchar_unlocked(c);
}
template <class T>
void writerLn(T x) {
  writer(x, '\n');
}
template <class T, class S>
void writerLn(T x, S y) {
  writer(x, ' ');
  writer(y, '\n');
}
template <class T, class S, class U>
void writerLn(T x, S y, U z) {
  writer(x, ' ');
  writer(y, ' ');
  writer(z, '\n');
}
template <class T, class S, class U, class V>
void writerLn(T x, S y, U z, V v) {
  writer(x, ' ');
  writer(y, ' ');
  writer(z, ' ');
  writer(v, '\n');
}
template <class T>
void writerArr(T x[], int n) {
  if (!n) {
    putchar_unlocked('\n');
    return;
  }
  for (int i = 0; i < (n - 1); i++) writer(x[i], ' ');
  writer(x[n - 1], '\n');
}
template <class T>
void writerArr(vector<T>& x) {
  writerArr(x.data(), (int)x.size());
}
template <class T>
void chmin(T& a, const T& b) {
  if (a > b) a = b;
}
template <class T>
void chmax(T& a, const T& b) {
  if (a < b) a = b;
}
template <class T>
T gcd(T a, T b) {
  return b ? gcd(b, a % b) : a;
}
template <class T>
T lcm(T a, T b) {
  return a / gcd(a, b) * b;
}
ll mod_pow(ll a, ll n, ll mod) {
  ll ret = 1;
  ll p = a % mod;
  while (n) {
    if (n & 1) ret = ret * p % mod;
    p = p * p % mod;
    n >>= 1;
  }
  return ret;
}
template <class T>
T extgcd(T a, T b, T& x, T& y) {
  for (T u = y = 1, v = x = 0; a;) {
    T q = b / a;
    swap(x -= q * u, u);
    swap(y -= q * v, v);
    swap(b -= q * a, a);
  }
  return b;
}
ll mod_inv(ll a, ll m) {
  ll x, y;
  extgcd<ll>(a, m, x, y);
  return (m + x % m) % m;
}
int len(ll n) {
  int ret = 0;
  while (n) ret++, n /= 10;
  return ret;
}
string construct(ll a, ll b, ll c, ll d) {
  string ans;
  if (a != 1) {
    ans += to_string(a);
    ans += "*";
  }
  ans += to_string(b) + "^" + to_string(c);
  if (d != 0) {
    ans += "+" + to_string(d);
  }
  return ans;
}
string solve(ll n) {
  if (n == 10000000000) {
    return "10^10";
  }
  if (n <= 999) {
    return to_string(n);
  }
  string ans = to_string(n);
  int loop = 0;
  for (ll b = 2; b < ((int)1e5); b++) {
    ll cur = b * b;
    int blen = len(b);
    for (int e = 2; cur <= n; e++, cur *= b) {
      int elen = len(e);
      int aaa = blen + elen + 1;
      if (aaa >= ((int)ans.size())) break;
      for (int a = 1; a <= 999; a++) {
        if (a * cur > n) break;
        ll bbb = aaa;
        if (a != 1) bbb += 1 + len(a);
        loop++;
        if (bbb >= ((int)ans.size())) break;
        ll diff = n - a * cur;
        if (diff) bbb += 1 + len(diff);
        if (bbb < ((int)ans.size())) {
          ans = construct(a, b, e, diff);
        }
      }
    }
  }
  for (int b = 2; b < 100; b++) {
    ll cur = b * b;
    int blen = len(b);
    for (int e = 2; cur <= n; e++, cur *= b) {
      if (n % cur != 0) break;
      ll a = n / cur;
      string tmp = construct(a, b, e, 0);
      if (((int)tmp.size()) < ((int)ans.size())) {
        ans = tmp;
      }
    }
  }
  for (int b = 2; b < 100; b++) {
    ll cur = b * b;
    for (int e = 2; cur <= n; e++, cur *= b) {
      for (int c = 2; c < 100; c++) {
        ll cur2 = cur * c * c;
        for (int f = 2; cur2 <= n; f++, cur2 *= c) {
          if (n % cur2 == 0) {
            ll a = n / cur2;
            if (a < 10) {
              char buf[20];
              sprintf(buf, "%d^%d*%d^%d", b, e, c, f);
              string tmp = buf;
              if (a != 1) {
                tmp += "*" + to_string(a);
              }
              if (((int)tmp.size()) < ((int)ans.size())) {
                ans = tmp;
              }
            }
          }
          if (n - cur2 < 10) {
            ll a = n - cur2;
            char buf[20];
            sprintf(buf, "%d^%d*%d^%d", b, e, c, f);
            string tmp = buf;
            if (a != 0) {
              tmp += "+" + to_string(a);
            }
            if (((int)tmp.size()) < ((int)ans.size())) {
              ans = tmp;
            }
          }
        }
      }
    }
  }
  for (int b = 2; b < 100; b++) {
    ll cur = b * b;
    for (int e = 2; cur <= n; e++, cur *= b) {
      for (int c = 2; c < 100; c++) {
        ll cur2 = c * c;
        for (int f = 2; cur + cur2 <= n; f++, cur2 *= c) {
          if ((n - cur2) % cur == 0) {
            ll a = (n - cur2) / cur;
            if (a < 10) {
              char buf[20];
              sprintf(buf, "%d^%d+%d^%d", b, e, c, f);
              string tmp = buf;
              if (a != 1) {
                tmp = to_string(a) + "*" + tmp;
              }
              if (((int)tmp.size()) < ((int)ans.size())) {
                ans = tmp;
              }
            }
          }
          if (n - cur2 - cur < 10) {
            ll a = n - cur2 - cur;
            char buf[20];
            sprintf(buf, "%d^%d+%d^%d", b, e, c, f);
            string tmp = buf;
            if (a != 0) {
              tmp += "+" + to_string(a);
            }
            if (((int)tmp.size()) < ((int)ans.size())) {
              ans = tmp;
            }
          }
        }
      }
    }
  }
  return ans;
}
void test() {
  for (ll i = ((int)1e5) + ((int)1e7); i <= ll(((int)1e9)) * 2; i++) {
    auto ans = solve(i);
    auto base = to_string(i);
    if (ans != base) {
      writerLn(ans);
    }
  }
}
int main() {
  ll n;
  reader(n);
  auto ans = solve(n);
  writerLn(ans);
  return 0;
}
