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 long long inf = (long long)5e18;
long long cal_len(long long x) {
  long long ret = 0;
  while (x) x /= 10, ret++;
  return ret;
}
struct node {
  long long B, T, V;
  bool operator<(const node &rhs) const {
    if (V == rhs.V)
      return cal_len(B) + cal_len(T) < cal_len(rhs.B) + cal_len(rhs.T);
    return V < rhs.V;
  }
  node() {}
  node(long long BB, long long TT, long long VV) : B(BB), T(TT), V(VV) {}
};
vector<node> f;
vector<long long> p;
long long n, a[10];
vector<long long> v[100001];
long long ans = 10000;
string str;
void init() {
  for (long long i = 2; i * i <= n; i++) {
    long long now = i;
    int Times = 1;
    while (now <= n) {
      v[i].push_back(now);
      f.push_back(node(i, Times, now));
      p.push_back(now);
      now *= i;
      Times++;
    }
  }
}
char fc(long long x) {
  if (x == 1) return '+';
  if (x == 2) return '*';
  return '^';
}
string fn(long long x) {
  string ret;
  while (x) {
    ret = (char(x % 10 + '0')) + ret;
    x /= 10;
  }
  return ret;
}
string get_str(long long len) {
  string ret;
  for (int i = 1; i <= len; i++) {
    if (i % 2 == 1) {
      string tmp = fn(a[i]);
      ret = ret + tmp;
    } else
      ret = ret + (char)fc(a[i]);
  }
  return ret;
}
void subtask1() {
  for (long long i = 2; i * i <= n; i++) {
    for (long long j = 0; j < (long long)v[i].size(); j++) {
      long long x = i, y = j + 1, val = v[i][j];
      long long d = n / val, r = n % val;
      if (d == 0) continue;
      if (d == 1 && r == 0) {
        long long tt = 1 + cal_len(x) + cal_len(y);
        if (ans > tt) {
          ans = tt;
          a[1] = x, a[2] = 3, a[3] = y;
          str = get_str(3);
        }
      }
      if (d == 1 && r != 0) {
        long long tt = 2 + cal_len(x) + cal_len(y) + cal_len(r);
        if (ans > tt) {
          ans = tt;
          a[1] = x, a[2] = 3, a[3] = y, a[4] = 1, a[5] = r;
          str = get_str(5);
        }
        int pos = lower_bound(p.begin(), p.end(), r) - p.begin();
        if (p[pos] == r) {
          long long C = f[pos].B, D = f[pos].T;
          tt = 3 + cal_len(x) + cal_len(y) + cal_len(C) + cal_len(D);
          if (ans > tt) {
            ans = tt;
            a[1] = x, a[2] = 3, a[3] = y, a[4] = 1, a[5] = C, a[6] = 3,
            a[7] = D;
            str = get_str(7);
          }
        }
      }
      if (d != 1 && r == 0) {
        long long tt = 2 + cal_len(x) + cal_len(y) + cal_len(d);
        if (ans > tt) {
          ans = tt;
          a[1] = x, a[2] = 3, a[3] = y, a[4] = 2, a[5] = d;
          str = get_str(5);
        }
        int pos = lower_bound(p.begin(), p.end(), d) - p.begin();
        if (p[pos] == d) {
          long long C = f[pos].B, D = f[pos].T;
          tt = 3 + cal_len(x) + cal_len(y) + cal_len(C) + cal_len(D);
          if (ans > tt) {
            ans = tt;
            a[1] = x, a[2] = 3, a[3] = y, a[4] = 2, a[5] = C, a[6] = 3,
            a[7] = D;
            str = get_str(7);
          }
        }
      }
      if (d != 1 && r != 0) {
        long long tt = 3 + cal_len(x) + cal_len(y) + cal_len(d) + cal_len(r);
        if (ans > tt) {
          ans = tt;
          a[1] = x, a[2] = 3, a[3] = y, a[4] = 2, a[5] = d, a[6] = 1, a[7] = r;
          str = get_str(7);
        }
      }
    }
  }
}
long long power(long long x, long long y) {
  long long ret = 1;
  while (y--) ret *= x;
  return ret;
}
void subtask2() {
  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++) {
            if (power(A, B) + power(C, D) + E == n) {
              if (ans > 9) {
                ans = 9;
                a[1] = A, a[2] = 3, a[3] = B, a[4] = 1, a[5] = C, a[6] = 3,
                a[7] = D, a[8] = 1, a[9] = E;
                str = get_str(9);
              }
            }
            if (power(A, B) + power(C, D) * E == n) {
              if (ans > 9) {
                ans = 9;
                a[1] = A, a[2] = 3, a[3] = B, a[4] = 1, a[5] = C, a[6] = 3,
                a[7] = D, a[8] = 2, a[9] = E;
                str = get_str(9);
              }
            }
            if (power(A, B) * power(C, D) + E == n) {
              if (ans > 9) {
                ans = 9;
                a[1] = A, a[2] = 3, a[3] = B, a[4] = 2, a[5] = C, a[6] = 3,
                a[7] = D, a[8] = 1, a[9] = E;
                str = get_str(9);
              }
            }
            if (power(A, B) * power(C, D) * E == n) {
              if (ans > 9) {
                ans = 9;
                a[1] = A, a[2] = 3, a[3] = B, a[4] = 2, a[5] = C, a[6] = 3,
                a[7] = D, a[8] = 2, a[9] = E;
                str = get_str(9);
              }
            }
          }
        }
      }
    }
  }
}
int main() {
  scanf("%lld", &n);
  ans = cal_len(n);
  str = fn(n);
  init();
  sort(f.begin(), f.end());
  sort(p.begin(), p.end());
  subtask1();
  if (ans == 10) subtask2();
  for (int i = 0; i < (int)str.size(); i++) printf("%c", str[i]);
  return 0;
}
