题目描述

算术基本定理可表述为：任何一个大于 $1$ 的自然数 $N$ ,如果 $N$ 不为质数，那么$N$ 可以唯一分解成有限个质数的乘积 : $N=P_1^{a1}P_2^{a_2}P_3^{a_3}......P_n^{a_n}$，这里 $P_1<P_2<P_3......<P_n$ 均为质数，其中指数 $a_i$ 是正整数。这样的分解称为 $N$ 的标准分解式。最早证明是由欧几里得给出的。

现在给定一个整数 $n$，请按照算术基本定理分解。对于 $p^i$，若指数 $i=1$，直接输出 "p" ，若 $i >1$ 输出为 "(p^i)",中间乘号输出"*"。例如 $24=2^3*3$，输出为"(2^3)*3"

输入格式

一个整数 $n$，满足 $2 \leq n \leq 10^9$ .

输出格式

按要求输出

152

(2^3)*19

998244353

998244353

数据规模与约定

$2 \leq n \leq 10^9$