Given an integer N, can you determine its prime factors?
Input
The input will contain a single integer N (2≤N≤106).
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.