Prime Factorization

You are given a positive integer \(n\). Your task is to compute the prime factorization of \(n\) and print it in a specified format.

The output should list the prime factors in increasing order. For each prime factor:

• If its exponent is 1, simply output the prime number.
• If its exponent is greater than 1, output it in the format prime^exponent (using the caret symbol '^').

For example:

• \(20 = 2^2 \times 5\) should be output as 2^2 5.
• \(100 = 2^2 \times 5^2\) should be output as 2^2 5^2.
• If \(n = 1\) then output an empty string.

Note: The prime factorization is unique for every integer greater than 1. Use trial division for factorization.

inputFormat

The input consists of a single integer \(n\) (\(1 \leq n \leq 10^9\)). The number \(n\) is given on the first line of input.

outputFormat

Output a single line containing the prime factorization of \(n\) in the specified format. If \(n=1\), output an empty line.

20

2^2 5