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!!