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;
template <class T>
void _R(T &x) {
  cin >> x;
}
void _R(int &x) { scanf("%d", &x); }
void _R(long long &x) { scanf("%lld", &x); }
void _R(double &x) { scanf("%lf", &x); }
void _R(char &x) { scanf(" %c", &x); }
void _R(char *x) { scanf("%s", x); }
void R() {}
template <class T, class... U>
void R(T &head, U &...tail) {
  _R(head);
  R(tail...);
}
template <class T>
void _W(const T &x) {
  cout << x;
}
void _W(const int &x) { printf("%d", x); }
void _W(const long long &x) { printf("%lld", x); }
void _W(const double &x) { printf("%.16f", x); }
void _W(const char &x) { putchar(x); }
void _W(const char *x) { printf("%s", x); }
template <class T, class U>
void _W(const pair<T, U> &x) {
  _W(x.first);
  putchar(' ');
  _W(x.second);
}
template <class T>
void _W(const vector<T> &x) {
  for (auto i = x.begin(); i != x.end(); _W(*i++))
    if (i != x.cbegin()) putchar(' ');
}
void W() {}
template <class T, class... U>
void W(const T &head, const U &...tail) {
  _W(head);
  putchar(sizeof...(tail) ? ' ' : '\n');
  W(tail...);
}
int MOD = 1e9 + 7;
void ADD(long long &x, long long v) {
  x = (x + v) % MOD;
  if (x < 0) x += MOD;
}
const int SIZE = 1e6 + 10;
const long long MAX_N = 10000000000LL;
long long mypow(long long x, long long y) {
  long long res = 1;
  while (y) {
    if (y & 1) {
      res *= x;
      res = min(res, MAX_N);
    }
    y >>= 1;
    x = x * x;
    x = min(x, MAX_N);
  }
  return res;
}
string an;
char tmp[SIZE];
void update() {
  string ss(tmp);
  if (((int)(ss).size()) < ((int)(an).size())) an = ss;
}
int dc[SIZE];
int main() {
  for (int i = (1); i < (SIZE); ++i) {
    dc[i] = 1 + dc[i / 10];
  }
  long long n;
  R(n);
  if (n == MAX_N) {
    W("100^5");
    return 0;
  }
  an = to_string(n);
  for (int a = (1); a <= (9); ++a)
    for (int b = (1); b <= (9); ++b)
      for (int c = (1); c <= (9); ++c)
        for (int d = (1); d <= (9); ++d)
          for (int e = (1); e <= (9); ++e) {
            if (a * mypow(b, c) + mypow(d, e) == n) {
              if (a != 1) {
                sprintf(tmp, "%d*%d^%d+%d^%d", a, b, c, d, e);
              } else {
                sprintf(tmp, "%d^%d+%d^%d", b, c, d, e);
              }
              update();
            }
          }
  for (int a = (1); a <= (9); ++a)
    for (int b = (1); b <= (9); ++b)
      for (int c = (1); c <= (9); ++c)
        for (int d = (1); d <= (9); ++d)
          for (int e = (1); e <= (9); ++e) {
            if (mypow(a, b) * mypow(c, d) + e == n) {
              sprintf(tmp, "%d^%d*%d^%d+%d", a, b, c, d, e);
              update();
            }
          }
  for (long long b = 2; b * b <= n; b++) {
    if (n % (b * b) == 0) {
      long long now = b * b;
      int c = 2;
      while (n % now == 0) {
        if (n == now) {
          sprintf(tmp, "%lld^%d", b, c);
        } else {
          sprintf(tmp, "%lld*%lld^%d", n / now, b, c);
        }
        now *= b;
        c++;
      }
      update();
    }
  }
  for (long long b = 2; b < 1000; b++) {
    long long v = b * b;
    for (long long c = 2; v <= n; c++, v *= b) {
      for (long long a = 1; a < 1000 && a * v <= n; a++) {
        sprintf(tmp, "%lld*%lld^%lld+%lld", a, b, c, n - a * v);
        update();
      }
    }
  }
  for (long long b = 2; b * b <= n; b++) {
    long long v = b * b;
    for (long long c = 2; v <= n; c++, v *= b) {
      sprintf(tmp, "%lld^%lld+%lld", b, c, n - v);
      update();
    }
  }
  for (long long a = 2; a < 1000; a++) {
    long long v1 = a * a;
    for (long long b = 2; v1 < n; b++, v1 *= a) {
      for (long long c = a; c < 1000; c++) {
        long long v2 = c * c;
        long long d = 2;
        while (v1 + v2 < n) {
          d++;
          v2 *= c;
        }
        if (v1 + v2 == n) {
          sprintf(tmp, "%lld^%lld+%lld^%lld", a, b, c, d);
          update();
        }
      }
    }
  }
  W(an);
  return 0;
}
