SPOJ.com - Problem FACTMULM

FACTMULM - Product of factorials (medium)

no tags

You need to find the product of the first n factorials, so 1! * 2! * ... * n! modulo p, where p=63303212889375877567328165411288303907410870625225931671654121339922293885519921.

Input

An integer T, denoting the number of testcases (T≤10). Each of the T following lines contains a positive integer, where

n≤ 10^8.

Output

Output T lines, the case number followed by the answer. See the sample output for the correct format!

Example

Input:
7
1
5
100
429
1000
1000000
100000000

Output:
Case 1: 1
Case 2: 34560
Case 3: 30320185692040509343149810686654647278680728299485184027723296362520679295668953
Case 4: 49116522183503229678644619968184124916695876848076217702050317922528502280661110
Case 5: 38310494067749735972957877453766730719859042112664856832928508845605975573300554
Case 6: 59623175509081913319809873890125269865036398088611331352359071382248773213856402
Case 7: 43046234475587180053977224639514165196068475389708692929440906111909653614719387

Submit solution!

hide comments

< Previous 1 2 Next >

	[Lakshman]: 2019-01-05 09:07:00 This problem was in my TODO list for long and now I have the solution, But my solution is not much convincing. Initially, I tried with prime and superfactorial prime factorization and all leade to TLE. My current solution heavily depends on the precomputed value which I think is not the expected solution. @Robert Gerbicz can you please tell me if other users also solved this problem the way I have done or are there really any algorithm which can be used to solve this problem. Thanks =(Francky)=> My solution is (at this time) the fastest python one, and use precomputed stuff, and many tricks; it is said by gerrob to use all know tricks. (comments below). Best regards ;-) Thanks, @Francky For now I have used only one trick. Last edit: 2019-01-06 16:50:00
	Raj Kumar Chauhan: 2015-02-01 07:09:59 TLE in python :( any special algo? (gerrob) O(Tn) algorithms will get only TLE. Last edit: 2015-02-01 18:27:41*
	Robert Gerbicz: 2014-08-26 13:21:21 @Francky: There is no more trick/idea. --ans(Francky)--> Thanks. Last edit: 2014-03-04 22:59:11
	Francky: 2014-03-03 01:15:56 @Robert Gerbicz : The 2013-09-09 17:43:39, you spoke about a new idea. Is it my last one, or do you have another ? Last edit: 2014-03-04 22:54:41
	Michael Kharitonov: 2013-09-12 13:16:58 @Robert Gerbicz: Number of test cases are not enough, result depends on luck. Again, 0.01 expected time difference and 0.25 real.(id=10009560,10009609) Last edit: 2013-09-12 13:18:18
	Michael Kharitonov: 2013-09-05 14:46:05 @Robert Gerbicz: 4 tests are not enough. My almost equal (~0.001 expected time difference) solutions gain different (~0.15) results. (gerrob) A total combined time of less than 2 sec. would be possible, every solution misses at least one idea. Last edit: 2013-09-09 17:43:39
	Michael Kharitonov: 2013-09-05 14:06:48 @Sidharth Gupta: Yes, it is possible to solve it in C/C++, but it is hard! My python solution is much easier. Last edit: 2013-09-05 15:50:55
	Miguel Oliveira: 2013-08-26 00:49:11 Thank you for checking this out and increase the time limit. My python knowledge is quite poor. I tried several things except exploiting the input distribution (there's not much point in doing that) and my code is a complete mess. This is one of those problems where I would really like to be able to read others code to learn how to code things efficiently in python.
	Robert Gerbicz: 2013-08-25 23:17:01 The last two files was uniform random, and you had TLE only on the last one. 10 n values is so small, it depends only on luck (or on some submissions) to get AC or TLE, as the distribution of n values has a small effect on running time. Increased the time limit on these files to 3.5 sec. ps. My sample solution has AC in 7.29 sec. (in python 3), but this hasn't used your trick, (used another trick). Last edit: 2013-08-25 23:22:53
	Miguel Oliveira: 2013-08-25 20:01:07 I'm clueless. I tried a few things like exploring the primes, optimize the modulo operations but these didn't improve anything. Could you give a hint? Either here or by e-mail if you prefer (it's on my profile). Thanks in advance

Submit solution!

Added by:	Robert Gerbicz
Date:	2013-08-23
Time limit:	2s-3.5s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64
Resource:	FACTMUL