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
Kid Algorist: 2014-11-06 13:55:45

Limit is beyond 10000.
Change code to adjust primes till 10007 to be safe.
WA for using primes till 9973, AC for 10009

ivar.raknahs: 2014-10-06 21:30:01

learned a new thing!
AC.

arun vinud: 2014-08-21 21:35:12

Very nice and easy problem :)

Anurag Mandilwar: 2014-08-07 14:23:14

Good problem!!

Gautam Kumar: 2014-02-19 20:12:06

@Amlesh Jayakumar
can u please tell me for which value my code is giving wrong answer.
My id is 11097375.
Got it..i was missing spaces..gud problem.

Last edit: 2014-02-19 20:14:45
heatOn: 2014-02-16 10:25:08

Strange , using long long int for all variables gives AC in 0 seconds but using int gives AC in 0.1.

Last edit: 2014-02-16 10:30:05
hiddenman: 2014-02-15 15:39:06

good 1..... :)

pika_pika: 2013-12-31 16:37:53

don't consider the limit as 10000. I used a dynamic limit of the input to run the code and sieve. AC now. and no need of EOF

Manu Narsaria: 2013-12-28 05:43:14

nyc problem...
how is it completed in 0.0sec in c/c++...

Blue Moon: 2013-12-27 17:59:44

Enjoyed doing it!!


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)