每个正整数都可以分解成素数的乘积，例如： $ 6= 2×3、20=2^2 × 5 $ 。现在，给定⼀个正整数 $ N $ ，请按要求输出它的因数分解式 $ 2 ≤ N ≤ 10^{12} $ 。

输入格式

输⼊第⼀⾏，包含⼀个正整数$N$。约定$2 \leq N \leq 10^{12}$。

输出格式

输出⼀⾏，为 $ N $ 的因数分解式。要求按质因数由⼩到⼤排列，乘号⽤星号  * 表⽰，且左右各空⼀格。当且仅当⼀个素数出现多次时，将它们合并为指数形式，⽤上箭头 ^ 表⽰，且左右不空格。

样例输入1

6

样例输出1

2 * 3

样例输入2

20

样例输出2

2^2 * 5

 样例输入3

23

样例输出3

23

提示