FACTMULM  Product of factorials (medium)
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
hide comments
Raj Kumar Chauhan:
20150201 07:09:59
TLE in python :(


Robert Gerbicz:
20140826 13:21:21
@Francky: There is no more trick/idea.


Francky:
20140303 01:15:56
@Robert Gerbicz : The 20130909 17:43:39, you spoke about a new idea. Is it my last one, or do you have another ?


Michael Kharitonov:
20130912 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: 20130912 13:18:18 

Michael Kharitonov:
20130905 14:46:05
@Robert Gerbicz: 4 tests are not enough. My almost equal (~0.001 expected time difference) solutions gain different (~0.15) results.


Michael Kharitonov:
20130905 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: 20130905 15:50:55 

Miguel Oliveira:
20130826 00:49:11
Thank you for checking this out and increase the time limit.


Robert Gerbicz:
20130825 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.


Miguel Oliveira:
20130825 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.


Sidharth Gupta:
20130825 14:36:41
Is it possible to solve this in C/C++? 
Added by:  Robert Gerbicz 
Date:  20130823 
Time limit:  2s3.5s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  FACTMUL 