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

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

hide comments
2013-08-25 14:36:41 Sidharth Gupta
Is it possible to solve this in C/C++?
2013-08-24 12:25:34 Miguel Oliveira
Thank you for the reply. The idea I was referring to was not the one i submitted. It was about exploring primes and didn't use any precomputation. I will work on the problem some more time :)
2013-08-24 07:36:45 Miguel Oliveira
is it possible to do this in a language like python without any precomputation?
this P is quite big and my idea (i guess i shouldn't describe it here) is too slow for these limits.

(gerrob): Without any precomputation I think that it is impossible. Solution in Python is possible, see the ranktable (changed the judge, it won't merge all languages). My sample solution is also in python 3.2.3, you need only one more idea to get AC (in python).

Last edit: 2013-08-24 07:52:25
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.