# Prime Factors

Stamford University Bangl...
Limits 1s, 512 MB

Given an integer $N$, can you determine its prime factors?

## Input

The input will contain a single integer $N$ ($2 \le N \le 10^6$).

## Output

Print the prime factors of $N$ in the following format:

N = f1 ^ p1 * f2 ^ p2 * f3 ^ p3 ...


For example, when $N = 20580$, you will print:

20580 = 2 ^ 2 * 3 ^ 1 * 5 ^ 1 * 7 ^ 3


Note that the prime factors are in ascending order. If a prime number is not a prime factor of $N$, then the prime number is omitted from the expression.

## Sample

InputOutput
20580

20580 = 2 ^ 2 * 3 ^ 1 * 5 ^ 1 * 7 ^ 3