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
2013-05-12 08:33:27 Ouditchya Sinha
Easy problem :)
2013-04-21 08:20:08 :-)
nice problem :-)
2013-02-02 06:36:13 Venkatesh Ganesan
Can you please tell me why my submission (ID 8638869) is WA ?
2012-10-24 23:20:47 Mitch Schwartz
Yes, each input file only contains one number. Jared's comment implied otherwise, and I hadn't bothered submitting before because to me it's not a very interesting problem. The problem statement is still unclear, but anyway it's not necessary to read until EOF.
2012-10-22 18:13:51 nikoo28
FOR EVERYONE WHO IS GETTING A WA...the value of N>(10^4) for some test cases...i was also a victim and it did cost me 6 WA's.. :@

Last edit: 2012-10-22 18:17:18
2012-10-22 15:37:42 S__L
Hi! Please check my solution. I just can't figure out why it gives a wrong answer!
solution id: 7908677
2012-10-20 17:04:21 nikoo28
sir please check my submission id..#7896221

my result exactly matches to that on
http://www.wolframalpha.com/input/?i=prime+factors+of+1000!

is there some problem in the output format..?

Last edit: 2012-10-20 17:14:39
2012-09-24 21:29:21 londondreams!!
how to output means we have to consider the space in between two factors? problem setter please mention!!
2012-08-21 10:13:52 fitcat
I think why people got confused because of this statement "Each test case ..."
In fact, there is only one test case per single test file.

@Amlesh: I know there are several test input files. But they are different with test cases. We are focused on one single test file. So, there is only one test case. Please rephrase the wording.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.