High School Programming League 2011/12

Consider a mathematical expression where you just have 2 types of operations: multiplication and division. The operands are either positive integers or the factorial of a positive integer. For example, a valid expression would be:  2*5!*10!/11!. Given such an expression, you have to calculate the prime factorization of it and to print it as the result. All primes should be in increasing order and their exponents should be non-zero (not necessarily positive) integers.

Input

In the first and only line you are given the expression. The sum of all integers which appear in the expression is less than or equal 1,000,000.

Output

Output the desired factorization. The output must be in the following form: p₀^a₀*p₁^a₁.....p_n^a_n, where p₀ < p₁ < ... p_n.

Example

Input:
2*5!*10!/11!

Output:
2^4*3^1*5^1*11^-1

Scoring

By solving this problem you score 10 points.