100708 - 因数分解
将一个正整数n分解为：n=a^b * c^d *...*x^y的形式。且底数从小到大排列 a < c < ... < x ；若指数 b,d...y 为1，则不表示为幂的形式。
Input
一行，一个正整数，表示n。
对于100%的数据：
2 \le n \le 1\cdot 10^6
Output
一行，即分解结果。
Examples
Input
360
Output
2^3*3^2*5
将一个正整数n分解为：n=a^b * c^d *...*x^y的形式。且底数从小到大排列 a < c < ... < x ；若指数 b,d...y 为1，则不表示为幂的形式。
一行，一个正整数，表示n。
对于100%的数据：
2 \le n \le 1\cdot 10^6
一行，即分解结果。
360
2^3*3^2*5