Problem Description

Every positive integer can be decomposed into a product of prime numbers, for example: $6=2\times 3$, $20=2^2\times5$.

Given a positive integer, please output its factorization according to the specified format.

Input Format

The first line of input contains a positive integer $N$. It is guaranteed that $2 \le N \le 10^{12}$.

Output Format

Output a single line, which is the factorization of $N$. The prime factors should be arranged in ascending order. The multiplication symbol should be represented by an asterisk * with one space on each side. When a prime number appears multiple times, it should be combined into an exponential form using the caret ^ symbol, with no spaces on either side.

Sample Input and Output

Sample Input #1

6

Sample Output #1

2 * 3

Sample Input #2

20

Sample Output #2

2^2 * 5

Sample Input #3

23

Sample Output #3

23

见题面 Input 部分

见题面 Output 部分