继续数论。。

Problem Description

WhereIsHeroFrom:            Zty,what are you doing ?

Zty:                                    Iwant to calculate N!......

WhereIsHeroFrom:            Soeasy! How big N is ?

Zty:                                    1<=N <=1000000000000000000000000000000000000000000000…

WhereIsHeroFrom:            Oh! Youmust be crazy! Are you Fa Shao?

Zty:                                    No.I haven's finished my saying. I just said I want to calculate N! mod 2009





Hint : 0! = 1, N! = N*(N-1)!

Input

Each linewill contain one integer N(0 <= N<=10^9). Process to end of file.

Output

For eachcase, output N! mod 2009

Sample Input

4 

5

Sample Output

24

120

/*****************************************************

数据规模  1<N<10^9，妥妥的要找规律了。。

从  N = 1  到N = 40  时还都能正常算出，(正常规律  num[i] = num[i-1] * i %2009;  (   1<N<10^9)，，，N 为40时，num[N] = 245，可以发现  245 * 41 = 10045 = 2009 * 5，

所以，就可以知道了，N>40时，输出全部为  0。。。

***********************************************************/

#include<stdio.h>

#include<iostream>

using namespace std;

int num[42];

void cal()

{

	num[0] = 1,num[1] = 1;

	for(int i = 2;i<42;i++)

		num[i] = num[i-1]*i%2009;

}

int main()

{

	int n;

	cal();

	while(cin>>n)

    {

        if(n>41)

            printf("%d\n",0);

        else

            printf("%d\n",num[n]);

    }

	return 0;

}