Prime Factors

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

20580

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