### ** primefactorization**

## Problem Description

Given an integer *n* where 2 ≤ *n* < 10^{12}, factorize it into its prime factors.

## Input

A single integer, *n*

For 100% of the testcases, *n* < 10^{12}

For 50% of the testcases, *n* < 10^{6}

For 30% of the testcases, *n* < 10^{3}

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