F. Отобразить число
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вася регулярно участвует в соревнованиях по программированию. Он уже привык к достаточно длинным условиям задач и научился быстро выделять важные предложения среди множества слов. Разумеется, ограничения на входные данные и другие числа в описании задачи — очень важная часть условий, например, разложить на простые множители число до 1000000 проще, чем число до 1000000000. Однако, Вася заметил, что зачастую запись числа получается очень длинной и сложной для восприятия. Может, авторы задачи могли ее сократить? Например, вместо 1000000 можно написать $$$10^{6}$$$, вместо 1000000000 — $$$10^{9}$$$, а вместо 1000000007 — $$$10^{9}+7$$$.

Вася решил, что запись числа для удобства восприятия должна подчиняться следующим правилам:

  • запись должна содержать только числа, операции сложения («+»), умножения («*») и возведения в степень («^»), в частности, использование скобок не допускается;
  • нельзя использовать несколько операций возведения в степень подряд, например, запись «2^3^4» недопустима;
  • значение записанного выражения должно равняться исходному числу;
  • запись должна содержать наименьшее возможное количество символов.

По заданному числу $$$n$$$ найдите для него эквивалентную запись, удобную для восприятия.

Входные данные

Единственная строка содержит натуральное число $$$n$$$ ($$$1 \leq n \leq 10\,000\,000\,000$$$).

Выходные данные

Вывести удобную для восприятия запись числа $$$n$$$. Если существует несколько таких записей, выведите любую из них.

Примеры
Входные данные
2018
Выходные данные
2018
Входные данные
1000000007
Выходные данные
10^9+7
Входные данные
10000000000
Выходные данные
100^5
Входные данные
2000000000
Выходные данные
2*10^9
Примечание

В третьем примере так же допустим ответ 10^10, тоже имеющий длину $$$5$$$.