题目描述

每个正整数都可以分解成若干个质数的乘积。

例如：

现在给定一个正整数 $N$，请按照要求输出它的质因数分解式。

输入格式

输入一行，包含一个正整数 $N$。

输出格式

输出一行，表示 $N$ 的质因数分解式。

输出时需要满足以下要求：

• 所有质因数按照从小到大的顺序排列；
• 不同质因数之间使用 * 分隔，即星号 * 左右各有一个空格；
• 如果某个质因数只出现一次，则直接输出该质因数；
• 如果某个质因数出现多次，则合并为指数形式，使用 ^ 表示，且 ^ 左右不留空格。

样例

6

2 * 3

20

2^2 * 5

23

23

数据范围

$2 \le N \le 10^{12}$。