给定一个不超过
[ 1 \le n \le 10^{12} ]
的正整数，请你输出它的 质因数分解。

若
[ n = p_1^{a_1} \cdot p_2^{a_2} \cdot \dots \cdot p_k^{a_k} ]
其中 (p_1 < p_2 < \cdots < p_k) 为从小到大排序的质数，则要求输出格式如下：

p1^a1 * p2^a2 * ... * pk^ak

当指数为 1 时，^1 可以省略。例如：

• 输入：12
  输出：2^2 * 3

• 输入：9973（为质数）
  输出：9973

📥 输入格式

输入包含一行，一个整数：

n

保证：

[ 1 \le n \le 10^{12} ]

📤 输出格式

输出一行，为整数 (n) 的质因数分解。

• 各质因数按从小到大排序；
• 指数为 1 时省略指数部分；
• 不同因数之间使用 " * " 分隔。

🔍 样例输入 1

12

样例输出 1

2^2 * 3

🔍 样例输入 2

9973

样例输出 2

9973