PTIME - Prime Time

For your math homework this week your teacher gave you five large numbers and asked you to find their prime factors. However these numbers aren't nearly large enough for someone with knowledge of programming like yourself. So you decide to take the factorial of each of these numbers. Recall that N! (N factorial) is the product of the integers from 1 through N (inclusive). It’s your job now to create a program to help you do your homework.

Input

Each test case contains a number N (2 ≤ N ≤ 10000).

Output

The output should contain a line representing the prime factorization of the factorial given number, which should be of the form: p1^e1 * p2^e2 * ... * pk^ek where p1, p2, ... pk are the distinct prime factors of the factorial of the given number in increasing order, and e1, e2, ... ek are their exponents.

Example

Input:
10

Output:
2^8 * 3^4 * 5^2 * 7^1

Added by:Amlesh Jayakumar
Date:2012-06-19
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:DWITE Programming Contest 2012 (Own Problem)

hide comments
2012-06-21 22:27:44 Rishi Mukherje
for python users: there are some extra whitespace lines which may create problem.
2012-06-21 22:27:44 Jared Deckard
Got TLE when expecting 1 number...
Each LINE contains a number N.
2012-06-21 22:27:44 devu
@Amlesh:-Just clarify the question to all the users that they need to read it till end of file and test case can be 1 or 5 or anything
2012-06-21 22:27:44 :D
Yes, I also read until EOF, but description is unclear.

Input should be something like:
"Input contains some lines. Each with exactly one number N (2<=N<=10000)."

And for output:
"For each test case ..."

test case != input file

Last edit: 2012-06-20 06:48:57
2012-06-21 22:27:44 xxx
Got AC !!!! gud prob ....:)
2012-06-21 22:27:44 Amlesh Jayakumar
@Devendra- Please look at the constraints again.
@Gaurav- I'm not too sure what's wrong either :S. Looks right from my end (I'll look into it a bit more later on).

Last edit: 2012-06-19 21:41:46
2012-06-21 22:27:44 Amlesh Jayakumar
There's only one N per testcase as indicated.
2012-06-21 22:27:44 Surya
Yeah! Read till EOF..else you'll get WA..
2012-06-21 22:27:44 jaans
@ :D :: i read upto EOF and got AC :)
2012-06-21 22:27:44 :D
It's pretty unclear how many test cases are per file. One or some read until EOF? Please clarify.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.