FACTMUL - Product of factorials

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

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

hide comments
2013-08-23 19:09:04 Aditya Kumar Akash
admin could you please tell what's wrong with my code ?
code number 9897528

Last edit: 2013-08-23 19:09:28
2013-08-23 14:07:17 Robert Gerbicz
I've just setup a medium version of this problem. See FACTMULM.
2013-08-23 12:51:31 Miguel Oliveira
@Mehmet i guess it depends on the value of n. why don't you try it out and set a problem on spoj if it turns out to be an interesting problem? :)

Last edit: 2013-08-23 12:51:42
2013-08-23 08:39:30 [Lakshman]
@Mehmet Inal Yes I think solution is possible with given constraints and with prime mod value but with one condition mod should be less than 10^9+7

Last edit: 2013-08-23 10:51:16
2013-08-23 01:27:04 mehmetin
Would a solution be possible if mod value was a prime, given the same constraints?
2013-08-22 19:15:37 [Lakshman]
MY algorithm also based on the same O(n) concept and my running time is 2.24.
2013-08-22 17:25:01 Federico Lebrón
Xsquare: This isn't the place to ask for help with problems. You can ask in the forum about them, or just keep trying to solve it by yourself. Writing in this area spoils the problem for others.

Lastly, asymptotics are not everything. I can tell you that doing a single loop with your "6*10^5" iterations does pass, with timing of at most 0.00, so you're doing something else wrong.
2013-08-22 15:26:55 Xsquare
How can a simple O(n) solution get TLE? where n is even less than 6*10^5 in my code!
2013-08-21 23:29:33 Miguel Oliveira
@Lakshman, note that 109546051211 is not a prime, that's the twist.
2013-08-21 18:40:51 Xsquare
Am getting WA by simple precomputation.. Any think taken to be care of besides mod value getting negative?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.