描述

P.s.对题目叙述不耐烦者可直接看彩字部分。

你知道，Quantum seals 虽然强大，但是极不稳定。每一个 Quantum seals 都有一个魔法特征值。（整数）当设置 Quantum seals 地区的魔法天候值（整数）为m时，魔法特征值为p(m)的 Quantum seals 将会崩解。

你查了一些资料，终于在一本魔法书上找到了p(m)的定义，其实非常简单（对于那个时代的人来说）：**p(m)的值为m的正因数个数（包括1和m本身）**
现在你知道当时Trin设置的 Quantum seals 的魔法特征值n，又知道设置 Quantum seals 地区的魔法天候值x服从Gauss-E分布（在Gauss-E分布中，x取较小的值的机会远大于取较大的值的机会），于是你已经知道了你现在最后要解决的问题，而它可以概括为一句话：
求满足p(x)=n的x的最小值。
现在，开始行动！

格式

输入格式

一个整数n。(n≤10^9)
输入数据保证n分解质因数后每个质因数不大于130

输出格式

最小的x的值的分解质因数形式。

分解后有多个相同的质因数的应表示为幂形式（仅一个时也要表示为a^1的形式），底数小的幂排在前面。

例：
设最小的x=49140=2*2*3*3*3*5*7*13，
则应输出:
2^2*3^3*5^1*7^1*13^1

样例1

样例输入1

8

样例输出1

2^3*3^1

限制

1s

提示

[注意事项]
1.P1229/P1310未AC者建议先将其AC
2.如果在阅读本题上,你出现了困难,那么也可以部分参考P1229/P1310

来源

灵渊是通往地下世界 - Flowering WonderLand 的通道。不久前被Trin（其实很久了...）使用符印 - Quantum seals 和一些其他的符印封锁了此处（关于这件事...下次再谈），原因是在一次事件中由于偶然的因素，Trin等5人破坏了灵渊的魔法平衡（灵渊的构造可以看作类似传说中的虫洞）。现状是，灵渊内灵力激荡且魔法属性极不稳定，常人如想通过它就会在半途被直接分解成魔法元素，即使有能抵抗这样情况的人通过，稍有不慎也会造成灵渊结构的直接性崩塌，和其一起消失于虚空。

就在Uff到达灵渊的前几个小时，灵渊入口的 Quantum seals 被破坏，Trin设置的魔法守卫立即将这一信息反馈给Trin等5人（当然，包括你）。而你刚刚解决完Uff的问题，但是你很清楚现在可不是能缓缓地躺下喝茶的时候。你立即开始着手关于 Quantum seals 为什么会被破坏的问题。

P.s.其实通过强大的时空魔法也可以到达 Flowering WonderLand。