The code

After figuring out the lock is indeed breakable, it is time to enter into the building. However for this we ACTUALLY need to enter the code into the number lock!

Input

The input is a single line, terminated with an end of line character which contains a single positive n integer at most 4000.

Output

The output is the prime decomposition of n! (n factorial) in an ascending order based on the primes.

• If a prime is at the 0th power, then we do not print it out.
• If a prime is at the 1st power, then we just simply print out the prime.
• If a prime is at least at the 2nd power, then we print it out as p^k, where p is the prime and k is the exponent.
• Between each terms there are one space character, followed by a * and then an other space character.

Example