primefactorization

Problem Description

Given an integer n where 2 ≤ n < 10¹², factorize it into its prime factors.

Input

A single integer, n

For 100% of the testcases, n < 10¹²
For 50% of the testcases, n < 10⁶
For 30% of the testcases, n < 10³

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