Description

据说今天是男神SL的生日，但是他很低调，轻轻地送了一道大水题…

就是传说中的 " N !"
Input
每一行包含一个整数N(0 <= N<=10^9).
Output
对于每个数，输出 N! mod 2009
Sample Input

4
5

Sample Output

24
120

正常思路：大于2009的阶层后mod2009都是0。
dalao思路：2009 = 41*49， 所以，不小于41的阶层后都是0.

#include<stdio.h>
#include<iostream>
#include<map>
#include<algorithm>
#include<cstring>
#include<string.h>
#include<string>
#include<math.h>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;
#define MAXN 100005
#define INF 0x3f3f3f3f//将近int类型最大数的一半，而且乘2不会爆int
#define MOD 2009

ll jie(ll n)        //2009 = 41*49
{
    ll cnt=1;
    for(ll i=1; i<=n; ++i)
        cnt = cnt*i%MOD;
    return cnt;
}

int main()
{
    int n;
    while(cin >> n)
    {
        if(n > 2009) puts("0");
        else cout << jie(n) << '\n';
    }
	return 0;
}