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 MOD = (int)1e9 + 7;
const int FFTMOD = 1007681537;
const int INF = (int)1e9;
const long long LINF = (long long)1e18;
const long double PI = acos((long double)-1);
const long double EPS = 1e-9;
inline long long gcd(long long a, long long b) {
  long long r;
  while (b) {
    r = a % b;
    a = b;
    b = r;
  }
  return a;
}
inline long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
inline long long fpow(long long n, long long k, int p = MOD) {
  long long r = 1;
  for (; k; k >>= 1) {
    if (k & 1) r = r * n % p;
    n = n * n % p;
  }
  return r;
}
template <class T>
inline int chkmin(T& a, const T& val) {
  return val < a ? a = val, 1 : 0;
}
template <class T>
inline int chkmax(T& a, const T& val) {
  return a < val ? a = val, 1 : 0;
}
inline long long isqrt(long long k) {
  long long r = sqrt(k) + 1;
  while (r * r > k) r--;
  return r;
}
inline long long icbrt(long long k) {
  long long r = cbrt(k) + 1;
  while (r * r * r > k) r--;
  return r;
}
inline void addmod(int& a, int val, int p = MOD) {
  if ((a = (a + val)) >= p) a -= p;
}
inline void submod(int& a, int val, int p = MOD) {
  if ((a = (a - val)) < 0) a += p;
}
inline int mult(int a, int b, int p = MOD) { return (long long)a * b % p; }
inline int inv(int a, int p = MOD) { return fpow(a, p - 2, p); }
inline int sign(long double x) { return x < -EPS ? -1 : x > +EPS; }
inline int sign(long double x, long double y) { return sign(x - y); }
string toString(long long k) {
  string res;
  while (k) {
    res += char('0' + k % 10);
    k /= 10;
  }
  reverse((res).begin(), (res).end());
  return res;
}
void chemthan() {
  long long n;
  cin >> n;
  if (n == 1e10) {
    cout << "100^5\n";
    return;
  }
  auto ff = [&](long long k) {
    int res = 0;
    while (k) res++, k /= 10;
    return res;
  };
  vector<pair<long long, pair<int, string> > > vals;
  pair<int, string> res = make_pair(ff(n), toString(n));
  for (int p = 2; (long long)p * p <= n; p++) {
    long long pp = p;
    int cnt = 1;
    while (pp <= n) {
      for (int i = (0); i < (10); ++i) {
        if (n >= i && (n - i) % pp == 0) {
          long long k = (n - i) / pp;
          string express;
          express += toString(p);
          if (cnt > 1) {
            express += "^" + toString(cnt);
          }
          if (k > 1) {
            express += "*";
            express += toString(k);
          }
          if (i) {
            express += "+";
            express += toString(i);
          }
          chkmin(res, make_pair(int((express).size()), express));
        }
      }
      for (int i = 1; pp <= n / i; i++) {
        string express;
        if (i > 1) {
          express += toString(i) + "*";
        }
        express += toString(p);
        if (cnt > 1) {
          express += "^" + toString(cnt);
        }
        long long t = n - i * pp;
        if (!t) {
          chkmin(res, make_pair(int((express).size()), express));
        } else {
          string ee = express + "+" + toString(t);
          chkmin(res, make_pair(int((ee).size()), ee));
        }
        if (int((express).size()) > 6) break;
        vals.push_back(
            make_pair(i * pp, make_pair(int((express).size()), express)));
      }
      if (pp > n / p) break;
      pp *= p, cnt++;
    }
  }
  for (int a = (2); a < (10); ++a)
    for (int b = (2); b < (10); ++b)
      for (int c = (2); c < (10); ++c)
        for (int d = (2); d < (10); ++d) {
          long long t = (long long)fpow(a, b) * fpow(c, d);
          if (t <= n) {
            long long m = n - t;
            string express;
            express += char('0' + a);
            express += "^";
            express += char('0' + b);
            express += "*";
            express += char('0' + c);
            express += "^";
            express += char('0' + d);
            if (m) {
              express += "+";
              express += toString(m);
            }
            chkmin(res, make_pair(int((express).size()), express));
          }
        }
  for (int i = (1); i < (1e5); ++i) {
    string t = toString(i);
    vals.push_back(make_pair(i, make_pair(int((t).size()), t)));
  }
  sort((vals).begin(), (vals).end());
  int k = lower_bound((vals).begin(), (vals).end(),
                      make_pair(n, make_pair(-INF, (string) ""))) -
          vals.begin();
  if (k < int((vals).size()) && vals[k].first == n) {
    chkmin(res, vals[k].second);
  }
  for (auto it : vals) {
    long long need = n - it.first;
    string express = it.second.second;
    if (need) {
      express += "+" + toString(need);
    }
    chkmin(res, make_pair(int((express).size()), express));
    int k = lower_bound((vals).begin(), (vals).end(),
                        make_pair(need, make_pair(-INF, (string) ""))) -
            vals.begin();
    if (k < int((vals).size()) && vals[k].first == need) {
      string express = it.second.second + "+" + vals[k].second.second;
      chkmin(res, make_pair(int((express).size()), express));
    }
  }
  cout << res.second << "\n";
}
int main(int argc, char* argv[]) {
  ios_base::sync_with_stdio(0), cin.tie(0);
  if (argc > 1) {
    assert(freopen(argv[1], "r", stdin));
  }
  if (argc > 2) {
    assert(freopen(argv[2], "wb", stdout));
  }
  chemthan();
  cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
  return 0;
}
