Prime Factors

Work out the prime factors of a given number.

Run 6

Input

5090000

Expected Output

5090000: 2^4 5^4 509