#include <iostream> using n

#include <iostream>
using namespace std;
const int maxn=50;
const int y=2009;
int main()
{
	int n,c[maxn][maxn],i,j,s=0;
	cin >> n; 
	c[0][0]=1;
	for(i=1;i<=n;i++)
	{
		c[i][0]=1;
		for(j=1;j<i;j++)
		c[i][j]=c[i-1][j-1]+c[i-1][j];
		c[i][i]=1;
	} 
	for(i=0;i<=n;i++)
	s=(s+c[n][i])%y;
	cout << s << endl;
	return 0;
}

输入： 17 

输出:_______