Prime Factorization

Every positive integer can be expressed as a product of prime numbers. For example, we have \(6=2\times3\) and \(20=2^{2}\times5\). Given a positive integer \(n\), output its prime factorization in the following format:

If \(n=1\), output 1=1. Otherwise, output n=p_1^{e_1}\times p_2^{e_2}\times\cdots\times p_k^{e_k} where each prime factor \(p_i\) is arranged in increasing order and if the exponent \(e_i=1\), the exponent is omitted.

inputFormat

The input consists of a single positive integer \(n\) (\(1 \le n \le 10^9\)).

outputFormat

Output the factorization of \(n\) in the format n=p_1^{e_1}\times p_2^{e_2}\times\cdots\times p_k^{e_k}, where if a prime factor appears only once, omit the exponent. For example, for \(n=6\) output 6=2\times3 and for \(n=20\) output 20=2^{2}\times5. If \(n=1\), output 1=1.

sample

6

6=2\times3