Problem Description
Given an integer n where 2 ≤ n < 1012, factorize it into its prime factors.
Input
A single integer, n
For 100% of the testcases, n < 1012
For 50% of the testcases, n < 106
For 30% of the testcases, n < 103
Output
On each line, output the prime factors of n in sorted order, with its power indicated. (See Sample Output)
Sample Input 1
120
Sample Output 1
2^3
3^1
5^1
Sample Input 2
331
Sample Output 2
331^1