题目描述：

每个合数都可以写成几个质数的若干次方相乘的形式，其中每个质数都是这个合数的因数，叫做这个合数的分解质因数。 例如:90=2^1 * 3^2 * 5^1 输入合数 n，输出对应的质因数分解式。

输入格式：

一个正整数n

输出格式：

输出以下形式: n=a1^r1 * a2^r2 * a3^r3 * ... * an^rn 其中an表示n的质因数，rn表示an的多少次方，注意*两边必须有空格，可忽略行末尾的空格

样例：

36

36=2^2 * 3^2

提示

对于100%的数据:4<=n<=100000000，且保证n是合数