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;
struct IO {
  char buf[(1 << 20)], *p1, *p2;
  char pbuf[(1 << 20)], *pp;
  IO() : p1(buf), p2(buf), pp(pbuf) {}
  inline char gc() {
    return getchar();
    if (p1 == p2) p2 = (p1 = buf) + fread(buf, 1, (1 << 20), stdin);
    return p1 == p2 ? ' ' : *p1++;
  }
  inline bool blank(char ch) {
    return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';
  }
  template <class T>
  inline void read(T &x) {
    register double tmp = 1;
    register bool sign = 0;
    x = 0;
    register char ch = gc();
    for (; !(ch >= '0' && ch <= '9'); ch = gc())
      if (ch == '-') sign = 1;
    for (; (ch >= '0' && ch <= '9'); ch = gc()) x = x * 10 + (ch - '0');
    if (ch == '.')
      for (ch = gc(); (ch >= '0' && ch <= '9'); ch = gc())
        tmp /= 10.0, x += tmp * (ch - '0');
    if (sign) x = -x;
  }
  inline void read(char *s) {
    register char ch = gc();
    for (; blank(ch); ch = gc())
      ;
    for (; !blank(ch); ch = gc()) *s++ = ch;
    *s = 0;
  }
  inline void read(char &c) {
    for (c = gc(); blank(c); c = gc())
      ;
  }
  template <class t>
  inline void write(t x) {
    if (x < 0)
      putchar('-'), write(-x);
    else {
      if (x > 9) write(x / 10);
      putchar('0' + x % 10);
    }
  }
} io;
const long long mod = 1e9 + 7;
const long long mo = 998244353;
const long long N = 5e5 + 5;
long long n, ans, P, BA, CS, Mul;
map<long long, long long> f;
inline long long ksm(long long x, long long y) {
  long long ans = 1ll;
  while (y) {
    if (y & 1ll) ans = ans * x;
    x = x * x;
    y >>= 1ll;
  }
  return ans;
}
inline long long calc(long long x) {
  if (!x) return 0;
  return (long long)log10(x) + 1;
}
signed main() {
  io.read(n);
  ans = calc(n);
  long long S = sqrt(n);
  for (long long i = (2); i <= (S); i++)
    for (long long j = (2); j <= (50); j++) {
      long long x = ksm(i, j);
      if (x > n) break;
      if (!f[x])
        f[x] = calc(i) + calc(j) + 1;
      else
        f[x] = min(f[x], calc(i) + calc(j) + 1);
    }
  long long base = 2;
  long long AA = 0, BB = 0, CC = 0, Else = 0, fll = 0, FF = 0;
  for (long long del = (0); del <= (10); del++) {
    long long goal = n - del;
    base = 2;
    for (;;) {
      if (base * base > goal) break;
      for (long long i = (2); i <= (50); i++) {
        long long x = ksm(base, i);
        if (x > goal) break;
        long long step = f[goal - x];
        if (!step && x != goal) continue;
        if (x == goal) {
          long long AD = calc(del) + (del > 0);
          if (calc(base) + calc(i) + 1 + AD < ans)
            ans = AD + calc(base) + calc(i) + 1, AA = base, BB = i, FF = del,
            CC = 0;
        } else {
          long long AD = calc(del) + (del > 0);
          if (calc(base) + calc(i) + 2 + step + AD < ans)
            ans = AD + calc(base) + calc(i) + 2 + step, AA = base, BB = i,
            CC = goal - x, Else = step, FF = del;
        }
      }
      base++;
    }
  }
  long long Ans1 = ans;
  long long AAA = 0, BBB = 0, CCC = 0, EElse = 0, FFF = 0;
  for (long long del = (0); del <= (10); del++) {
    long long goal = n - del;
    base = 2;
    for (;;) {
      if (base * base > goal) break;
      for (long long i = (1); i <= (50); i++) {
        long long x = ksm(base, i);
        if (x > goal) break;
        if (goal % x) continue;
        long long step = f[goal / x];
        if (!step && x != goal) continue;
        if (x == goal) {
          long long AD = calc(del) + (del > 0);
          if (calc(base) + calc(i) + 1 + AD < ans)
            ans = AD + calc(base) + calc(i) + 1, AAA = base, BBB = i, FFF = del,
            CCC = 0;
        } else {
          long long AD = calc(del) + (del > 0);
          if (calc(base) + calc(i) + 2 + step + AD < ans)
            ans = AD + calc(base) + calc(i) + 2 + step, AAA = base, BBB = i,
            CCC = goal / x, EElse = step, FFF = del;
        }
      }
      base++;
    }
  }
  long long Ans2 = ans;
  P = n;
  base = 2;
  for (;;) {
    if (base * base > n) break;
    for (long long i = (1); i <= (50); i++) {
      long long x = ksm(base, i);
      if (x > n) break;
      long long rem = n / x;
      long long A = calc(rem);
      if (rem == 1) A = 0;
      long long B = calc(n - rem * x);
      if (f[n - rem * x]) B = min(B, f[n - rem * x]);
      long long C = calc(i);
      long long D = calc(base);
      if (n - rem * x) B++;
      if (i > 1) C++;
      if (A > 1) A++;
      if (A + B + C + D < ans) {
        ans = A + B + C + D;
        P = n - rem * x;
        BA = base;
        CS = i;
        Mul = rem;
      }
    }
    base++;
  }
  if (ans == Ans2 && AAA && BBB) {
    printf("%lld^%lld", AAA, BBB);
    long long FFA = 0, FFB = 0;
    if (FFF) {
      long long len = calc(FFF);
      if (f[FFF] < len) {
        for (long long i = (2); i <= (S); i++)
          for (long long j = (2); j <= (50); j++) {
            long long x = ksm(i, j);
            if (x > FFF) break;
            if (x == FFF) {
              if (calc(i) + calc(j) + 1 == f[FFF]) FFA = i, FFB = j;
            }
            if (FFA && FFB) break;
          }
      }
    }
    if (CCC) {
      putchar('*');
      long long DD = 0, EE = 0;
      for (long long i = (2); i <= (S); i++)
        for (long long j = (2); j <= (50); j++) {
          long long x = ksm(i, j);
          if (x > n) break;
          if (x == CCC) {
            if (calc(i) + calc(j) + 1 == EElse) DD = i, EE = j;
          }
          if (DD && EE) break;
        }
      printf("%lld^%lld", DD, EE);
      if (FFF) {
        putchar('+');
        if (FFA)
          printf("%lld^%lld", FFA, FFB);
        else
          printf("%lld", FFF);
      }
    } else if (FFF) {
      putchar('+');
      if (FFA)
        printf("%lld^%lld", FFA, FFB);
      else
        printf("%lld", FFF);
    }
    return 0;
  }
  if (ans == Ans1 && AA && BB) {
    printf("%lld^%lld", AA, BB);
    long long FFA = 0, FFB = 0;
    if (FF) {
      long long len = calc(FF);
      if (f[FF] < len) {
        for (long long i = (2); i <= (S); i++)
          for (long long j = (2); j <= (50); j++) {
            long long x = ksm(i, j);
            if (x > FF) break;
            if (x == FF) {
              if (calc(i) + calc(j) + 1 == f[FF]) FFA = i, FFB = j;
            }
            if (FFA && FFB) break;
          }
      }
    }
    if (CC) {
      putchar('+');
      long long DD = 0, EE = 0;
      for (long long i = (2); i <= (S); i++)
        for (long long j = (2); j <= (50); j++) {
          long long x = ksm(i, j);
          if (x > n) break;
          if (x == CC) {
            if (calc(i) + calc(j) + 1 == Else) DD = i, EE = j;
          }
          if (DD && EE) break;
        }
      printf("%lld^%lld", DD, EE);
      if (FF) {
        putchar('+');
        if (FFA)
          printf("%lld^%lld", FFA, FFB);
        else
          printf("%lld", FF);
      }
    } else if (FF) {
      putchar('+');
      if (FFA)
        printf("%lld^%lld", FFA, FFB);
      else
        printf("%lld", FF);
    }
    return 0;
  }
  if (P) {
    long long FFA = 0, FFB = 0;
    long long len = calc(P);
    if (f[P] < len) {
      for (long long i = (2); i <= (S); i++)
        for (long long j = (2); j <= (50); j++) {
          long long x = ksm(i, j);
          if (x > P) break;
          if (x == P) {
            if (calc(i) + calc(j) + 1 == f[P]) FFA = i, FFB = j;
          }
          if (FFA && FFB) break;
        }
    }
    if (FFA)
      printf("%lld^%lld", FFA, FFB);
    else
      printf("%lld", P);
  }
  if (BA) {
    if (P)
      printf("+%lld^%lld", BA, CS);
    else
      printf("%lld^%lld", BA, CS);
  }
  if (Mul > 1) printf("*%lld", Mul);
  return 0;
}
