Write the prime factorization of \(n\) using exponents.

Input

One line containing \(n\).

The input satisfies:

• \(2 \le n \le 10^12\)

Output

Print factors in increasing order using p^e, joined by *.

Example

Input

6685621

Output

6685621^1