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

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

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

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