题目背景

数学课上，老师告诉大家一条重要的定理：任何一个大于 $1$ 的正整数，都能唯一地写成若干个素数相乘的形式。小航觉得很有意思，想写个程序自动完成这件事。

题目描述

众所周知，每个大于 $1$ 的正整数都能表示成若干素数相乘的形式，例如 $6=2\times 3$，$20=2^2\times 5$。

现在给定一个正整数 $N$，请你帮小航输出它的素因数分解式。

输入格式

输入仅一行，包含一个正整数 $N$。约定 $2 \le N \le 10^{12}$。

输出格式

输出一行，为 $N$ 的素因数分解式。要求素因数按从小到大的顺序排列，相邻两个因数之间用星号 * 连接，星号左右各空一格；当某个素数恰好出现一次时直接写出它本身，当出现两次及以上时合并写成指数形式，底数与指数之间用上箭头 ^ 连接，^ 左右均不空格。

样例

6

2 * 3

20

2^2 * 5

23

23