Problem1210--22-循环-2-算算n！

1210: 22-循环-2-算算n！

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MB

Solved: 53Submit: 4758Statistics

Description

Alice：Bob你在干什么？

Bob：我在计算n的阶乘求余2009后的结果，即s=n!%2009

Alice：n有多大啊？

Bob：0≤n≤1000000000  

Alice：你疯了吧

Bob：放心，我会应用求余运算的性质的，即(axb)%c等价于((a%c)x(b%c))%c，而且n最多也才109 

Input

多组样例，输入一个整数n(0 ≤n≤109)

Output

输出一个数，表示输入数的阶乘求余2009后的结果。

Sample Input Copy 

4

Sample Output Copy 

24

HINT

0! = 1, n! =n*(n-1)!

Source/Category

 
Submit