Hyper-Prime Expression

Time Limit: 5 Seconds    Memory Limit: 32768 KB
Special Judge

Consider a special expression defined as follows:

Digits 1, 2, 3, 5, 7 are all legal expressions;
If a is a legal expressions, a! is a legal expression;
If a and b are both legal expressions, (a+b), (a*b) and (a^b) are all legal expressions.

Hyper-prime expressions are such expression defined above that uses minimal number of digits for a specific value. For example, (((3*(2*2))^2)*5) and 3!! are both legal expressions for 720, but the latter is a hyper-prime expression while the former is not.

WishingBone thinks it's too difficult to decompose a number in this way. He needs a program.

Input

One integer n (0 < n <=20000) per line - the number which you are to decompose into hyper-prime expression.

Process to the end of file.

Output

One expression per line, with no spaces embedded or around.

There might be several acceptable expressions for a same n. You may choose to print any of them.

Sample Input

1
14
720

Sample Output

1
(2*7)
3!!

Submit

Source: WishingBone's Contest #1