因数分解

难度：T2

【知识点：质因数分解】

前置知识：整除、循环、函数

题目描述

给定整数 $N$，将它写成质数相乘的形式。相同质因数合并，用字符 ^ 连接质因数和出现次数；次数为 $1$ 时不输出 ^1。不同质因数按从小到大的顺序输出，用 * 连接，星号两边各一个空格。

规则说明

素数也叫质数，指大于 $1$、正因数只有 $1$ 和自身的整数。因数是能整除原数的正整数；质因数是其中为质数的因数。$1$ 不是素数。例如 $12=2\times2\times3$，它的质因数是 $2$ 和 $3$。

输入格式

一行一个整数 $N$。

输出格式

一行分解式。严格按照题目描述输出，不要在开头、结尾添加星号。

样例输入

72

样例输出

2^3 * 3^2

数据范围

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