← 返回题目列表

Codeforces · 991/F

F. 简洁明了

中文机器翻译题面 查看原题

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$$$。