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;
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
const long long LIM = 10000000000LL;
struct SA {
  int p, x;
  long long val;
  int olen, nlen;
  SA(int p, int x, long long val, int olen, int nlen)
      : p(p), x(x), val(val), olen(olen), nlen(nlen) {}
};
bool operator<(const SA &a, const SA &b) {
  if (a.val != b.val) return a.val < b.val;
  return a.nlen < b.nlen;
}
long long mlt(long long a, long long b) {
  return a > LLONG_MAX / b ? LLONG_MAX : a * b;
}
long long inc(long long a, long long b) {
  return a > LLONG_MAX - b ? LLONG_MAX : a + b;
}
long long pw(int a, int b) {
  long long ret = 1;
  for (int i = (0); i < (b); ++i) ret = mlt(ret, a);
  return ret;
}
vector<SA> sa;
int digits(long long x) {
  if (x == 0) return 1;
  int ret = 0;
  while (x > 0) ++ret, x /= 10;
  return ret;
}
void gensa() {
  for (int p = 2; (1LL << p) <= LIM; ++p) {
    for (int x = 2;; ++x) {
      long long cur = 1;
      for (int i = (0); i < (p); ++i) cur = mlt(cur, x);
      if (cur > LIM) break;
      int olen = digits(cur), nlen = digits(x) + 1 + digits(p);
      if (nlen < olen) sa.push_back(SA(p, x, cur, olen, nlen));
    }
  }
  sort(sa.begin(), sa.end());
  int nsa = 0;
  for (int i = (0); i < (((int)(sa).size())); ++i)
    if (nsa == 0 || sa[i].val != sa[nsa - 1].val) sa[nsa++] = sa[i];
  while (((int)(sa).size()) > nsa) sa.pop_back();
}
void solve(long long x) {
  vector<string> opt;
  for (int a = (1); a < (10); ++a)
    for (int b = (1); b < (10); ++b)
      for (int c = (1); c <= (10); ++c)
        for (int d = (1); d < (10); ++d)
          for (int e = (1); e < (10); ++e) {
            long long val1 = mlt(mlt(a, pw(b, c)), pw(d, e));
            if (val1 == x) {
              char buff[20];
              sprintf(buff, "%d*%d^%d*%d^%d", a, b, c, d, e);
              opt.push_back(buff);
            }
            long long val2 = inc(a, mlt(pw(b, c), pw(d, e)));
            if (val2 == x) {
              char buff[20];
              sprintf(buff, "%d+%d^%d*%d^%d", a, b, c, d, e);
              opt.push_back(buff);
            }
            long long val3 = inc(inc(a, pw(b, c)), pw(d, e));
            if (val3 == x) {
              char buff[20];
              sprintf(buff, "%d+%d^%d+%d^%d", a, b, c, d, e);
              opt.push_back(buff);
            }
            long long val4 = inc(mlt(a, pw(b, c)), pw(d, e));
            if (val4 == x) {
              char buff[20];
              sprintf(buff, "%d*%d^%d+%d^%d", a, b, c, d, e);
              opt.push_back(buff);
            }
          }
  {
    char buff[20];
    sprintf(buff, "%lld", x);
    opt.push_back(buff);
  }
  for (int i = (0); i < (((int)(sa).size())); ++i)
    if (sa[i].val == x) {
      char buff[20];
      sprintf(buff, "%d^%d", sa[i].x, sa[i].p);
      opt.push_back(buff);
    }
  for (int i = (0); i < (((int)(sa).size())); ++i)
    for (int j = (0); j < (i); ++j) {
      long long cur = mlt(sa[i].val, sa[j].val);
      if (cur > LIM) break;
      if (cur == x) {
        char buff[20];
        sprintf(buff, "%d^%d*%d^%d", sa[j].x, sa[j].p, sa[i].x, sa[i].p);
        opt.push_back(buff);
      }
    }
  for (int i = (0); i < (((int)(sa).size())); ++i)
    if (x % sa[i].val == 0) {
      long long c = x / sa[i].val;
      char buff[20];
      sprintf(buff, "%lld*%d^%d", c, sa[i].x, sa[i].p);
      opt.push_back(buff);
    }
  for (int i = (0); i < (((int)(sa).size())); ++i)
    if (x > sa[i].val) {
      long long c = x - sa[i].val;
      char buff[20];
      sprintf(buff, "%lld+%d^%d", c, sa[i].x, sa[i].p);
      opt.push_back(buff);
    }
  {
    int l = 0, r = ((int)(sa).size()) - 1;
    while (l <= r) {
      long long cur = inc(sa[l].val, sa[r].val);
      if (cur == x) {
        char buff[20];
        sprintf(buff, "%d^%d+%d^%d", sa[l].x, sa[l].p, sa[r].x, sa[r].p);
        opt.push_back(buff);
        ++l, --r;
      } else if (cur < x)
        ++l;
      else
        --r;
    }
  }
  for (int i = (0); i < (((int)(sa).size())); ++i)
    if (sa[i].nlen == 3) {
      for (int c = (1); c < (1000); ++c)
        for (int d = (1); d < (1000); ++d) {
          long long val = inc(mlt(c, sa[i].val), d);
          if (val == x) {
            char buff[20];
            sprintf(buff, "%d*%d^%d+%d", c, sa[i].x, sa[i].p, d);
            opt.push_back(buff);
          }
        }
    }
  for (int i = (0); i < (((int)(sa).size())); ++i)
    if (sa[i].nlen == 4) {
      for (int c = (1); c < (100); ++c)
        for (int d = (1); d < (100); ++d) {
          long long val = inc(mlt(c, sa[i].val), d);
          if (val == x) {
            char buff[20];
            sprintf(buff, "%d*%d^%d+%d", c, sa[i].x, sa[i].p, d);
            opt.push_back(buff);
          }
        }
    }
  for (int i = (0); i < (((int)(sa).size())); ++i)
    if (sa[i].nlen == 5) {
      for (int c = (1); c < (10); ++c)
        for (int d = (1); d < (10); ++d) {
          long long val = inc(mlt(c, sa[i].val), d);
          if (val == x) {
            char buff[20];
            sprintf(buff, "%d*%d^%d+%d", c, sa[i].x, sa[i].p, d);
            opt.push_back(buff);
          }
        }
    }
  string ret = opt[0];
  for (int i = (0); i < (((int)(opt).size())); ++i)
    if (((int)(opt[i]).size()) < ((int)(ret).size())) ret = opt[i];
  printf("%s\n", ret.c_str());
}
void run() {
  long long x;
  scanf("%lld", &x);
  solve(x);
}
int main() {
  gensa();
  run();
  return 0;
}
