FACTMUL - Product of factorials

no tags 

You need to find the product of first n factorials 1! * 2! * ... * n! modulo 109546051211.

Input

One integer n (1 <= n <= 10000000)

Output

The answer.

Example

Input:
5

Output:
34560

hide comments
smso: 2020-04-22 09:39:14

Biggest difficulty is that mod=109546051211 is so big that mod^2 already overflows.

divyansh_soni: 2018-09-21 16:20:29

CRT rocks...

hunnychauhan: 2017-07-19 18:08:52

prefer python rather than c or c++...

proficient: 2017-01-05 12:35:20

Adhoc in Pypy. AC in one-go.

Shubham Pandey: 2016-07-07 18:02:07

use python , and there is no need to preprocess for just a single input

Last edit: 2016-07-07 18:03:07
Sarthak Munshi: 2016-06-12 12:55:16

Preprocess factorials and use binary exponention . peace !

thierry: 2016-05-07 11:23:31

No success using Pike so far (and the corresponding java performs well).
weird °_°'

Yash: 2016-04-30 14:19:36

Nice Question :)

dark_lord1: 2015-12-26 21:11:55

For c/c++ users, hint : (115*118)%119 = [ 115*(64 + 32+ 16 + 0 + 4 + 2 + 0) ]%119...Similar to exponential modulus

darkhire21: 2015-11-15 05:35:28

With same logic python 3.0 tle and 2.7 AC but how ?


Added by:Ashot Minasyan
Date:2013-08-20
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64