Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

HS11EXPR - Problem with an expression

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: p0^a0*p1^a1.....pn^an, where p0 < p1 < ... pn.

Example

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

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

Scoring

By solving this problem you score 10 points.


Added by:Damir Ferizovic
Date:2011-09-05
Time limit:0.400s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ADA95 ASM32 ASM64 BASH BF C CSHARP C++ 4.3.2 CPP C99 CLPS CLOJURE LISP sbcl LISP clisp D ERL FSHARP FORTRAN GO HASK ICON JAVA JS-RHINO LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PERL6 PHP PIKE PRLG-swi PYTHON PYTHON3 RUBY SCALA SCM guile SCM qobi ST TCL WHITESPACE
Resource:High School Programming League 2011/12

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.