/*
#include <stdio.h>
int m[201]={};
int f(int n)
{
if(m[n]!=0)
return m[n];
if(n<=2)
return m[n]=1;
return m[n]=(f(n-1)+f(n-2))%10009;
}
int main()
{
int n;
scanf("%d",&n);
printf("%d",f(n));
return 0;
}
s(k,n)= s(k-1,1) + s(k-1,2) + ... s(k-1,n)
= (s(k-1,1) + ...+s(k-1,n-1)) + s(k-1,n)
= s(k,n-1) +s(k-1,n)
*/
/*
#include <stdio.h>
int m[15][15]={};
int SuperSum(int k, int n)
{
if(m[k][n]!=0)return m[k][n];
if(k==0)
return m[0][n]=n;
if(n==0)
return m[k][0]=0;
return m[k][n]=SuperSum(k,n-1)+SuperSum(k-1,n);
}
int main()
{
int k,n,i,j;
while(scanf("%d %d", &k, &n)!=EOF)
printf("%d\n", SuperSum(k, n));
return 0;
}
*/
/*
#include <stdio.h>
int m[100001]={};
int f(int n)
{
if(m[n])
return m[n];
if(n<=2)
return n;
if(n==3)
return 4;
return m[n]=(f(n-1)+f(n-2)+f(n-3))%1000;
}
int main()
{
int n;
scanf("%d",&n);
printf("%d",f(n));
return 0;
}
*/