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

hide comments
Prakhar Gupta: 2013-12-15 20:16:13

strange....using sieve to calculate prime upto 10000 gave WA, but using sieve upto prime just greater than 10000 gave AC....no need of EOF

NoName: 2013-12-04 11:47:15

one time work

Amlesh Jayakumar: 2013-11-21 06:42:38

None of the inputs exceed 10000 (as mentioned in the problem statement).

Last edit: 2013-11-21 06:42:50
shringi: 2013-09-14 07:36:13

the value of N is greater than mentioned...got one wrong answer for that

P_Quantum: 2013-08-30 05:30:55

Nice One..!! My 100th prblm.. :)

Rana Saha: 2013-08-23 00:09:43

That was Fun! :D

shashank khare: 2013-08-22 18:02:47

There is space before and after *.also no need of EOF costed me 1 WA...

Last edit: 2013-08-22 18:08:44
DEXTER: 2013-08-09 09:45:27

50!! :)

Nishant Gupta: 2013-08-03 17:01:36

sieve works fine here.....

ROHIT KUMAR: 2013-08-03 15:04:43

n this question brings me to 50:)
gud ques... jst take care of the PRESENTATION error ...


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)