You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小 Z 是一个非常聪明的小朋友，他对于数学有着特别的热爱。有一天，他在课堂上学习了阶乘的概念后，产生了一个奇妙的想法——如果有一个整数 $x$，那么 $x$ 的阶乘写作 $x!=x * (x-1) * (x - 2) * \cdots * 2 * 1$。

这个简单的定义，在小 Z 看来拥有无穷的魅力。他开始尝试用阶乘来定义新的运算，他相信这可以将复杂的数学问题简化。

一天，小 Z 坐在公园里学习时，灵机一动写下了这样一个运算式 $f(x)=x^{1} * (x-1)^{2} * (x-2)^{3} * \cdots * 2^{x-1} * 1^{x}$。

又由于小 Z 比较喜欢质数，他听说大数的质因子分解很难，现在小 Z 想知道这个运算式取 $n$ 时的质因子分解形式。即将 $f(n)$ 进行质因数分解后的形式是什么？

输入格式

一行一个正整数 $n$，表示 $f(n)$。

输出格式

一行一个字符串，表示 $f(n)$ 的质因数分解形式，要求按照质因数从小到大排列，当指数为 $1$ 时不需要输出指数。

具体格式请参见样例理解。

样例 #1

样例输入 #1

5

样例输出 #1

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

提示

【样例解释】

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

【数据范围】

对于 $30\%$ 的数据，满足 $2\le n \le 1000$。

对于 $70\%$ 的数据，满足 $2\le n < 10^6$。

对于 $100\%$ 的数据，满足 $5\le n \le 10^7$。