题目描述

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

$N=p1$^$a1$$* p2$^$a2$$* \dots * pk$^$ak$。

注意: 如果 $N=1$ 则输出 $1=1$ 。

在程序的实际输出时， $p1$^$a1$写作： $p1 \text{\textasciicircum} a1$ 。

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

比如：如果 $N=100$ ，那么输出： $100=2 \text{\textasciicircum} 2*5 \text{\textasciicircum} 2$ 。

再比如：如果 $N=20$ ，那么输出： $20=2 \text{\textasciicircum} 2*5$ 。

输入

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

输出

按题意输出分解结果。

样例

100

100=2^2*5^2

来源

因子