#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

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

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 100 | 10 | 1s | 32MB | Average |

2 | 0 | 2 | 1s | 32MB | Average |

### Judge Compile Command

g++-7 ans.cpp -o primefactorization -Wall -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512