Prime Factorization

You are given a positive integer \(n\). Your task is to print its prime factorization in the following format: p1^e1 * p2^e2 * ..., where each pi is a prime factor of \(n\) and ei is its exponent. Even if the exponent is 1, it must be displayed as ^1.

For example, if \(n = 28\), the correct output is 2^2 * 7^1.

Note: The output factors must be shown in increasing order of the prime numbers.

inputFormat

The input consists of a single line with one integer \(n\) (\(1 \le n \le 10^{12}\)).

outputFormat

Output the prime factorization of \(n\) in the format described above. There should be no extra characters or spaces apart from the required format.

28

2^2 * 7^1