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.BufferedInputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.*;

public class F {

	static long N;
	static int bestLen;
	static String bestRes;
	static HashMap<Long, ArrayList<Long>> facMap = new HashMap<Long, ArrayList<Long>>();
	static TreeSet<Long> pows = new TreeSet<Long>();
	static HashMap<Long, String> powMap = new HashMap<Long, String>();
	static HashMap<Long, String> noAddMap = new HashMap<Long, String>();
	
	public static void main(String[] args) {
		JS in = new JS();

		N = in.nextLong();
		bestRes = N+"";
		
		ArrayList<Long> curList = new ArrayList<Long>();
		for(long i = 2; i*i <= 10000000000L; i++) {
			long cur = i;
			for(long pow = 2;;pow++) {
				cur *= i;
				String s = i+"^"+pow;
				String sss = ""+cur;
				if(sss.length() < s.length()) s = sss;
				if(cur > 10000000000L) break;

				if(cur <= N) {
					curList.add(cur);

				}
				
				pows.add(cur);
				String curS = powMap.get(cur);
				if(curS == null || curS.length() > s.length()) {
					powMap.put(cur, s);
				}
			}
		}
		for(Long cur : curList) {
			long c = N/cur;
			String s1 = powMap.get(cur);
			if(c != 1) s1 += ("*"+c);
			if(N-cur*c != 0) {
				long aa = N-cur*c;
				if(pows.contains(aa)) s1 += "+"+powMap.get(aa);
				else s1 += "+"+(N-cur*c);
			}
			if(s1.length() < bestRes.length()) {
				bestRes = s1;
			}
		}
		
		for(Long ll : pows) {
			long other = N-ll;
			if(pows.contains(other)) {
				String s1 = goNoAdd(ll)+"+"+goNoAdd(other);
				if(s1.length() < bestRes.length()) bestRes = s1;
			}	
		}
		for(Long ll : pows) {
			if(N%ll != 0) {
				for(int plus = 1; plus <= 9; plus++) {
					long N2 = N-plus;
					if(N2%ll != 0)continue;
					long other = N2/ll;
					if(pows.contains(other)) {
						String s1 = goNoAdd(ll)+"*"+goNoAdd(other)+"+"+plus;
						if(s1.length() < bestRes.length()) bestRes = s1;
					}	
				}
				continue;
			}
			long other = N/ll;
			if(pows.contains(other)) {
				String s1 = goNoAdd(ll)+"*"+goNoAdd(other);
				if(s1.length() < bestRes.length()) bestRes = s1;
			}	
		}
		String best2 = goNoAdd(N);
		if(best2.length() < bestRes.length()) bestRes = best2;
		
		System.out.println(bestRes);
		
	}
	
	//we want val*C <= N with highest C
	static long bs(long lo, long hi, long val) {
		if(lo==hi) return lo;
		if(lo+1 == hi) {
			if(val*hi <= N) return hi;
			return lo;
		}
		long mid = (lo+hi)/2;
		if(val*mid <= N) return bs(mid, hi, val);
		return bs(lo, mid, val);	
	}
	
	static String goNoAdd(long val) {
		if(noAddMap.containsKey(val)) return noAddMap.get(val);
		String best = ""+val;
		if(pows.contains(val)) {
			String s1 = powMap.get(val);
			if(s1.length() < best.length()) best = s1;
		}
		for(Long fac : factors(val)) {
			String s1 = goNoAdd(val/fac);
			String s2 = goNoAdd(fac);
			if(s1.length()+s2.length()+1 < best.length()) {
				best = s1+"*"+s2;
			}
		}	
		noAddMap.put(val, best);
		return best;
	}
	
	
	static ArrayList<Long> factors (long n){
		if(facMap.containsKey(n)) return facMap.get(n);
		ArrayList<Long> res = new ArrayList<Long>();
		for(long i = 2; i*i < n; i++) {
			if(n%i == 0) {
				res.add(i);
			}
		}
		facMap.put(n,res);
		return res;
	}
	
	
	static class JS{
		public int BS = 1<<16;
		public char NC = (char)0;
		byte[] buf = new byte[BS];
		int bId = 0, size = 0;
		char c = NC;
		double num = 1;
		BufferedInputStream in;
		
		public JS() {
			in = new BufferedInputStream(System.in, BS);
		}
		
		public JS(String s) throws FileNotFoundException {
			in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
		}
		
		public char nextChar(){
			while(bId==size) {
				try {
					size = in.read(buf);
				}catch(Exception e) {
					return NC;
				}				
				if(size==-1)return NC;
				bId=0;
			}
			return (char)buf[bId++];
		}
		
		public int nextInt() {
			return (int)nextLong();
		}
		
		public long nextLong() {
			num=1;
			boolean neg = false;
			if(c==NC)c=nextChar();
			for(;(c<'0' || c>'9'); c = nextChar()) {
				if(c=='-')neg=true;
			}
			long res = 0;
			for(; c>='0' && c <='9'; c=nextChar()) {
				res = (res<<3)+(res<<1)+c-'0';
				num*=10;
			}
			return neg?-res:res;
		}
		
		public double nextDouble() {
			double cur = nextLong();
			return c!='.' ? cur:cur+nextLong()/num;
		}
		
		public String next() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c>32) {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}
		
		public String nextLine() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c!='\n') {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}

		public boolean hasNext() {
			if(c>32)return true;
			while(true) {
				c=nextChar();
				if(c==NC)return false;
				else if(c>32)return true;
			}
		}
	}
}
