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.
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.TreeMap;
import java.util.StringTokenizer;
import java.util.Map;
import java.util.Map.Entry;
import java.io.BufferedReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author kessido
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        FConciseAndClear solver = new FConciseAndClear();
        solver.solve(1, in, out);
        out.close();
    }

    static class FConciseAndClear {
        public void solve(int testNumber, InputReader in, PrintWriter out) {
            long n = in.NextLong();
            Bunker bunker = new Bunker();
            out.println(bunker.getBest(n));
        }

        public static abstract class Expresion {
            abstract long val();

            abstract int length();

            public static int length(long x) {
                int res = 0;
                while (x != 0) {
                    res++;
                    x /= 10;
                }
                return res;
            }

        }

        public static class SimpleExpresion extends FConciseAndClear.Expresion {
            long base;

            public SimpleExpresion(long base) {
                this.base = base;
            }

            long val() {
                return base;
            }

            int length() {
                return FConciseAndClear.Expresion.length(base);
            }


            public String toString() {
                return "" + base;
            }

        }

        public static class PowerExpresion extends FConciseAndClear.Expresion {
            long base;
            long exp;

            public PowerExpresion(long base, long exp) {
                this.base = base;
                this.exp = exp;
            }


            public long val() {
                return MathExtentions.power(base, exp);
            }


            public int length() {
                return FConciseAndClear.Expresion.length(base) + 1 + FConciseAndClear.Expresion.length(exp);
            }


            public String toString() {
                return "" + base + "^" + exp;
            }

        }

        public static class MultiplicationExpresion extends FConciseAndClear.Expresion {
            FConciseAndClear.Expresion left;
            FConciseAndClear.Expresion right;

            public MultiplicationExpresion(FConciseAndClear.Expresion left, FConciseAndClear.Expresion right) {
                this.left = left;
                this.right = right;
            }

            long val() {
                return left.val() * right.val();
            }

            int length() {
                return left.length() + right.length() + 1;
            }


            public String toString() {
                return left + "*" + right;
            }

        }

        public static class AddExpresion extends FConciseAndClear.Expresion {
            FConciseAndClear.Expresion left;
            FConciseAndClear.Expresion right;

            public AddExpresion(FConciseAndClear.Expresion left, FConciseAndClear.Expresion right) {
                this.left = left;
                this.right = right;
            }

            long val() {
                return left.val() + right.val();
            }

            int length() {
                return left.length() + right.length() + 1;
            }


            public String toString() {
                return left + "+" + right;
            }

        }

        class Bunker {
            TreeMap<Long, FConciseAndClear.Expresion> hm = new TreeMap<>();

            private FConciseAndClear.Expresion get(long n) {
                FConciseAndClear.Expresion ret = hm.get(n);
                if (ret == null) ret = new FConciseAndClear.SimpleExpresion(n);
                return ret;
            }

            private void put(long n, FConciseAndClear.Expresion ex) {
                if (ex.length() < FConciseAndClear.Expresion.length(n)) {
                    FConciseAndClear.Expresion exx = hm.get(n);
                    if (exx == null || exx.length() > ex.length()) {
                        hm.put(n, ex);
                    }
                }
            }

            private void addAllPowers(long n) {
                for (long i = 2; i * i <= n; i++) {
                    for (int j = 2; ; j++) {
                        FConciseAndClear.Expresion nex = new FConciseAndClear.PowerExpresion(i, j);
                        long x = nex.val();
                        if (x > n) break;
                        put(x, nex);
                    }
                }
            }

            private FConciseAndClear.Expresion findBestAdd(FConciseAndClear.Expresion best, long n) {
                for (FConciseAndClear.Expresion exp : hm.values()) {
                    long x = exp.val();
                    long needed = n - x;
                    Map.Entry<Long, FConciseAndClear.Expresion> exp2 = hm.floorEntry(needed);
                    if (exp2 == null) break;
                    FConciseAndClear.Expresion exp22 = exp2.getValue();
                    FConciseAndClear.Expresion addsExp = new FConciseAndClear.AddExpresion(exp, exp22);
                    x = addsExp.val();
                    if (n != x) {
                        addsExp = new FConciseAndClear.AddExpresion(new FConciseAndClear.SimpleExpresion(n - x), addsExp);
                    }
                    best = best(best, addsExp);
                }
                return best;
            }

            private FConciseAndClear.Expresion findBestMult(FConciseAndClear.Expresion best, long n) {
                for (FConciseAndClear.Expresion expresion : hm.values()) {
                    FConciseAndClear.Expresion mult = expresion;
                    long x = expresion.val();
                    long nx = n / x;
                    if (nx > 1) {
                        mult = new FConciseAndClear.MultiplicationExpresion(new FConciseAndClear.SimpleExpresion(nx), mult);
                        x *= nx;
                    }
                    if (n != x) {
                        mult = new FConciseAndClear.AddExpresion(mult, get(n - x));
                    }
                    best = best(best, mult);
                }
                return best;
            }

            private FConciseAndClear.Expresion best(FConciseAndClear.Expresion o, FConciseAndClear.Expresion o1) {
                return (o1 == null || (o != null && o1.length() < o.length())) ? o1 : o;
            }

            private FConciseAndClear.Expresion findBestMult2(FConciseAndClear.Expresion best, long n) {
                for (FConciseAndClear.Expresion expresion : hm.values()) {
                    FConciseAndClear.Expresion mult = expresion;
                    long x = mult.val();
                    long needed = n / x;
                    Map.Entry<Long, FConciseAndClear.Expresion> multByEntry = hm.floorEntry(needed);
                    if (multByEntry == null) break;
                    FConciseAndClear.Expresion multBy = multByEntry.getValue();
                    mult = new FConciseAndClear.MultiplicationExpresion(mult, multBy);
                    x = mult.val();
                    if (x != n) {
                        mult = new FConciseAndClear.AddExpresion(mult, new FConciseAndClear.SimpleExpresion(n - x));
                    }
                    best = best(mult, best);
                }
                return best;
            }

            private FConciseAndClear.Expresion getBest(long n) {
                hm.clear();
                addAllPowers(n);
                FConciseAndClear.Expresion best = new FConciseAndClear.SimpleExpresion(n);
                best = findBestAdd(best, n);
                best = findBestMult(best, n);
                best = findBestMult2(best, n);
                return best;
            }

        }

    }

    static class InputReader {
        BufferedReader reader;
        StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine(), " \t\n\r\f,");
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public long NextLong() {
            return Long.parseLong(next());
        }

    }

    static class MathExtentions {
        public static long power(final long x, final long y) {
            if (y == 0)
                return 1;

            long p = power(x, y / 2);
            p = (p * p);

            if (y % 2 == 0)
                return p;
            else
                return (x * p);
        }

    }
}

