e-olymp
Competitions

Azerbaijan Programming Olympiad - 2nd Stage preparation

The Lesson of mathematics

At the beginning of each lesson the teacher of mathematics Guzel Zakievna wrote on the blackboard natural number n. While the lesson the students are trying to find as much as possible prime divisors of that number. At the end of the lesson generous Guzel Zakievna gives sweets to all those who have found the maximum number of prime divisors. A pupil Vassya loves sweets and asks you to help him to have some from Guzel Zakievny today. You are given number n, to withdraw all of its prime factors in the degree to which they are found in this number.

Input

One positive integer n109.

Output

Print all the prime divisors of numbers in ascending order and specify for each subgroup the extent to which it occurs among the n, if its degree is greater than unity. The output format must match the same.

Time limit 1 second
Memory limit 128 MiB
Input example #1
3240
Output example #1
2^3*3^4*5
Source SCS 2009