说明

给定一个整数$N$，找出它的所有质因子，并按如下格式输出：

$N=p_1^{a1}×p_2^{a2}×…×p_k^{ak}$ 注意: 如果 N=1 则输出 1=1。

在程序的实际输出时，$p_1^{a1}$写作：p1^a1

其中 $p_k$ 是质因子，应按照递增顺序排列，$ak$是$p_k$的指数，如果$ak$为 1，则不必输出。

比如：如果$N$=100，那么输出：100=2^2*5^2。

再比如：如果$N$=20，那么输出：20=2^2*5。

输入格式

一个整数$N（N≤2^{31}-1）$

输出格式

按题意输出分解结果。

样例

100

100=2^2*5^2