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 M = 2e5, INF = 0x3fffffff;
template <typename T>
void read(T &x) {
  bool neg = false;
  unsigned char c = getchar();
  for (; (c ^ 48) > 9; c = getchar())
    if (c == '-') neg = true;
  for (x = 0; (c ^ 48) < 10; c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
  if (neg) x = -x;
}
struct power {
  int a, b, l;
  long long c;
  bool operator<(power x) const { return c < x.c; }
} p[M];
long long n;
int m, len, pos;
char ans[20];
int length(int x) { return x == 0 ? 0 : length(x / 10) + 1; }
int length(long long x) { return x == 0 ? 0 : length(x / 10) + 1; }
void uni(int &m) {
  int del = 0;
  for (int i = 0; i + del < m;) {
    if (i + del == 0 || p[i + del].c != p[i - 1].c) {
      p[i] = p[i + del];
      ++i;
    } else {
      if (p[i + del].l < p[i - 1].l) p[i - 1] = p[i + del];
      ++del;
    }
  }
  m -= del;
}
int find(long long x) {
  int l = 0, r = m, mid;
  while (r - l > 1) {
    mid = (l + r) >> 1;
    if (x < p[mid].c)
      r = mid;
    else
      l = mid;
  }
  return l;
}
int main() {
  read(n);
  for (int i = 2; (long long)i * i <= n; ++i) {
    int ll = length(i);
    long long k = (long long)i * i;
    for (int j = 2; k <= n; k *= i, ++j) {
      p[m].a = i;
      p[m].b = j;
      p[m].c = k;
      p[m++].l = ll + length(j) + 1;
    }
  }
  sort(p, p + m);
  uni(m);
  len = length(n);
  sprintf(ans, "%lld", n);
  for (int i = 0, i_end = m; i < i_end; ++i)
    if (n % p[i].c == 0) {
      if (n == p[i].c) {
        if (p[i].l < len) {
          len = p[i].l;
          sprintf(ans, "%d^%d", p[i].a, p[i].b);
        }
      } else {
        int tmp, r = find(n / p[i].c);
        if (p[r].c == n / p[i].c) {
          tmp = p[r].l + 1 + p[i].l;
          if (tmp < len) {
            len = tmp;
            sprintf(ans, "%d^%d*%d^%d", p[r].a, p[r].b, p[i].a, p[i].b);
          }
        }
        tmp = length(n / p[i].c) + 1 + p[i].l;
        if (tmp < len) {
          len = tmp;
          sprintf(ans, "%lld*%d^%d", n / p[i].c, p[i].a, p[i].b);
        }
      }
    }
  for (int i = 0, i_end = m; i < i_end; ++i) {
    int tmp = p[i].l + 1 + length(n - p[i].c), r;
    if (tmp < len) {
      len = tmp;
      sprintf(ans, "%d^%d+%lld", p[i].a, p[i].b, n - p[i].c);
    }
    r = find(n - p[i].c);
    if (p[r].c != n - p[i].c) continue;
    tmp = p[i].l + 1 + p[r].l;
    if (tmp < len) {
      len = tmp;
      sprintf(ans, "%d^%d+%d^%d", p[i].a, p[i].b, p[r].a, p[r].b);
    }
  }
  for (int i = 0, i_end = m; i < i_end; ++i) {
    int tmp = length(n / p[i].c) + 1 + p[i].l + 1 + length(n % p[i].c);
    if (tmp < len) {
      len = tmp;
      sprintf(ans, "%lld*%d^%d+%lld", n / p[i].c, p[i].a, p[i].b, n % p[i].c);
    }
  }
  if (len == 10)
    for (int i1 = 2, i1_end = 10; i1 < i1_end; ++i1) {
      int j1 = i1;
      for (int i2 = 2, i2_end = 10; i2 < i2_end; ++i2) {
        j1 *= i1;
        for (int i3 = 2, i3_end = 10; i3 < i3_end; ++i3) {
          int j2 = i3;
          for (int i4 = 2, i4_end = 10; i4 < i4_end; ++i4) {
            j2 *= i3;
            for (int i5 = 1, i5_end = 10; i5 < i5_end; ++i5) {
              long long val = (long long)j1 * j2 + i5;
              int tmp = 9;
              if (val == n && tmp < len) {
                len = tmp;
                sprintf(ans, "%d^%d*%d^%d+%d", i1, i2, i3, i4, i5);
              }
              val = (long long)i5 * j1 + j2;
              if (val == n && tmp < len) {
                len = tmp;
                sprintf(ans, "%d*%d^%d+%d^%d", i5, i1, i2, i3, i4);
              }
            }
          }
        }
      }
    }
  puts(ans);
  return 0;
}
