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.util.ArrayList;
import java.util.Scanner;
import java.lang.StringBuilder;
import java.util.Arrays;
import java.util.Stack;
import java.util.TreeMap;
public class Test11   {  
    public static int getdig(long a) {
        long l = a;
        int ans = 0;
        while (l > 0)  {
            l = l / 10;
            ans++;
        }    
        return ans;
    }    
    public static int getdig2(long a) {
        if (a == 0) return 0;
        long l = a;
        int ans = 0;
        while (l > 0)  {
            l = l / 10;
            ans++;
        }    
        return ans + 1;
    }    
    public static void main(String[] Args)   {
        Scanner sc = new Scanner(System.in);
        Long n = sc.nextLong(); 
         if (n == 1000000000) System.out.println("10^10");
         else {
             String ans = n.toString();
             int min = getdig(n);
             //case 1 pw * pw + num
             for (Integer a = 2; a <= 999; a++)  {
                 long pow1 = a * a;
                 Integer b = 2; 
                 while (pow1 <= n / 1000)  {
                     for (Integer c = 2; c <= 9; c++)  {
                         long pow2 = c * c;
                         Integer d = 2;
                         while (pow1 * pow2 < n)  {
                             Long res = n - pow1 * pow2;
                             if (getdig2(res) + getdig(a) +getdig(b) + getdig(c) + getdig(d) + 3 < min)  {
                                 min = getdig2(res) + getdig(a) +getdig(b) + getdig(c) + getdig(d) + 3;
                                 if (res == 0) ans = a.toString() + '^' + b.toString() + '*' + c.toString() + '^' + d.toString();
                                 else ans = a.toString() + '^' + b.toString() + '*' + c.toString() + '^' + d.toString() + '+' + res.toString();
                             }
                             pow2 *= c;
                             d++;
                         }    
                     } 
                     pow1 *= a;
                     b++;
                 }    
             }
             //case 2: pw + num;
             for (Long a = new Long("2"); a <= 399999; a++)  {
                 Integer b = 2;
                 long pw = a * a;
                 while (pw <= n)  {
                     Long res = n - pw;
                     if (getdig2(res) + getdig(a) + getdig(b) + 1< min)  {
                         min = getdig2(res) + getdig(a) + getdig(b) + 1;
                         if (res == 0) ans = a.toString() + '^' + b.toString();
                          else ans = a.toString() + '^' + b.toString() + '+' + res.toString();
                     }    
                     pw *= (long)a;
                     b++;
                 }    
             }
             //case 3: pw + pw + num
             for (Long a = new Long("2"); a <= 999; a++)  {
                 Integer b= 2;
                 long pw = a * a;
                 while (pw <= n)  {
                     for (Long c = new Long("2"); c <= 99; c++)  {
                         Integer d = 2;
                         long pw2 = c * c;
                         while (pw2 + pw<= n)  {
                             
                             Long res = n - pw - pw2;
                             if (getdig2(res) + getdig(a) + getdig(b) + getdig(c) + getdig(d) + 3< min)  {
                                 min = getdig2(res) + getdig(a) + getdig(b) + getdig(c) + getdig(d) + 3;
                                if (res == 0) ans = a.toString() + '^' + b.toString() + '+' + c.toString() + '^' + d.toString();
                                 else ans = a.toString() + '^' + b.toString() + '+' + c.toString() + '^' + d.toString() + '+' + res.toString();
                             }
                             pw2 *= c;
                             d++;
                         }                         
                     }
                     pw *= a;
                     b++;
                 }   
             }    
             //case 4 : pw + pw * num
             for (Integer a = 2; a <= 9; a++)  {
                 Integer b= 2;
                 long pw = a * a;
                 while (pw <= n && b <= 9)  {
                     for (Integer c = 2; c <= 9; c++)  {
                         Integer d = 2;
                         long pw2 = c * c;
                         while (pw2 + pw<= n && d <= 9)  {
                             
                             Long res = (n - pw) / pw2;
                             if (min == 10 && res <= 9 && (n - pw) % pw2  == 0)  {
                                 min = 9;
                                 ans = a.toString() + '^' + b.toString() + '+' + c.toString() + '^' + d.toString() + '*' + res.toString();
                             }
                             pw2 *= c;
                             d++;
                         }                         
                     }
                     pw *= a;
                     b++;
                 }   
             } 
             //case 5 : pw * pw * num
              for (Integer a = 2; a <= 9; a++)  {
                 Integer b= 2;
                 long pw = a * a;
                 while (pw <= n && b <= 9)  {
                     for (Integer c = 2; c <= 9; c++)  {
                         Integer d = 2;
                         long pw2 = c * c;
                         while (pw2 * pw<= n && d <= 9)  {
                             
                             Long res = (n / pw) / pw2;
                             if (min == 10 && res <= 9 && n  == pw * pw2 * res)  {
                                 min = 9;
                                 ans = a.toString() + '^' + b.toString() + '*' + c.toString() + '^' + d.toString() + '*' + res.toString();
                             }
                             pw2 *= c;
                             d++;
                         }                         
                     }
                     pw *= a;
                     b++;
                 }   
             }
            //case 6: pw *  num + num
              for (Long a = new Long("2"); a <= 99999; a++)  {
                  Integer b = 2;
                  long pw = a * a;
                  while (pw <= n)  {
                      Long num1 = n / pw;
                      Long num2 = n % pw;
                      if (min > getdig(num1) + getdig(a) + getdig(b) + getdig2(num2) + 2)  {
                          min = getdig(num1) + getdig(a) + getdig(b) + getdig2(num2) + 2;
                          if (num2 == 0)ans = a.toString() + '^' + b.toString() + '*' +num1.toString();
                          else ans = a.toString() + '^' + b.toString() + '*' +num1.toString() + '+' + num2.toString();
                      }    
                      b++;
                      pw *= a;
                  }    
              }    
         System.out.println(ans);
         }             
   }
}