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

hide comments
Raj Kumar Chauhan: 2015-02-01 07:09:59

TLE in python :(
any special algo?
(gerrob) O(T*n) 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

Sidharth Gupta: 2013-08-25 14:36:41

Is it possible to solve this in C/C++?


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