eolymp
bolt
Try our new interface for solving problems
Problems

Канонічний розклад

Канонічний розклад

Time limit 1 second
Memory limit 64 MiB

Дано десятковий запис натурального числа до 200 цифр, всі прості дільники якого не перевищують 500 000. Створіть програму, яка виведе канонічний розклад цього числа на прості множники в порядку їх зростання.

Input data

Єдиний рядок вхідних даних містить натуральне десяткове число з кількістю цифр, що не перевищує 200.

Output data

Результат повинен містити єдиний рядок, що містить канонічний розклад заданого числа з урахуванням правил виведення (див. приклад).

Examples

Input example #1
31
Output example #1
31
Input example #2
1024
Output example #2
2^10
Input example #3
84
Output example #3
2^2*3*7