It is required to decompose the integer N into prime factors, presenting it as a product of powers of prime factors and output the result in ascending order.
Input
The input is a number N (\(2 <= N <= 10^9\)).
Output
Output prime factorization of N.
Examples
| # |
Input |
Output |
| 1 |
2 |
2 |
| 2 |
1008 |
2^4*3^2*7 |