Vasya 是编程竞赛的定期参与者,并且在寻找长语句中的重要句子方面拥有丰富的经验。当然,数字约束很重要 - 小于 1000000 的数字的因式分解比小于 1000000000 的数字更容易。但是,有时乍一看很难理解该数字。可以缩短吗?例如,您可以写 $$$10^{6}$$$,而不是 1000000,而不是 1000000000 —$$$10^{9}$$$,而不是 1000000007 — $$$10^{9}+7$$$。
Vasya 决定,为了简洁起见,符号应遵循以下几条规则:
- 符号只能由数字、加法(“+”)、乘法(“*”)和幂(“^”)运算组成,特别是禁止使用大括号;
- 禁止连续使用多个求幂运算,例如,写“2^3^4”是不可接受的;
- 结果表达式的值等于初始数字;
- 符号应包含最少量的符号。
给定 $$$n$$$,找到它的等效简洁符号。
输入
唯一的行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 10\,000\,000\,000$$$)。
输出
输出数字 $$$n$$$ 的简洁表示法。如果有多个简明符号,则输出其中任何一个。
示例
输入 #1
2018
输出 #1
2018
输入 #2
1000000007
输出 #2
10^9+7
输入 #3
10000000000
输出 #3
100^5
输入#4
2000000000
输出#4
2*10^9
注意
第三个样本允许答案 10^10 的长度也为 $$$5$$$。