题目

$wanan$哥哥是美羊羊的舔 $gou$ , 为了得到美羊羊 , $wanan$一次次的向美羊羊表白 , 但美羊羊每次都会问他一个问题 , 如果答对了就做他女朋友(哈哈这是不可能的) 。

还记得上次跟美羊羊表白 , 美羊羊问的问题是求一个数$\pmb{x}$的阶乘($\pmb{x!=x*(x-1)*(x-2)*...*2*1}$), $wanan$没能答上来 , 因此十分痛心 , 闭关修炼100天后再一次向美羊羊表白了 。

这次美羊羊让给出了一个式子$\pmb{f(x)=x^1*(x-1)^2*(x-2)^3...2^{x+1} *1^x}$, 让$wanan$计算这个运算式取$n$时的质因子分解形式。 $wanan$哥哥现在急需你的帮助$！$

输入

每个样例一行 , 一个整数$\pmb{x(2\le x \le10^6)}$, 表示运算式的输入。

输出

输出一个字符串 , 表示$f(x)$的质因子分解形式 , 要求按照因子从小到大排列 , 当指数为 $1$ 时应该忽略指数 , 具体格式要求参见样例。

样例

5

f(5)=2^8*3^3*5

样例解释

$\pmb{f(5)=2^4*3^3*4^2*5^1=2^8*3^3*5}$