/*
#include<stdio.h>
void f(int a)
{
if(a>1) f(a/2);
printf("%d", a%2);
}
int main()
{
int a;
scanf("%d", &a);
f(a);
return 0;
}*/
/*
#include<stdio.h>
int memo[201]={};
int f(int a)
{
if(memo[a]!=0) return memo[a]; //계산한 적 있는 것은 다시 계산 x
if(a==1 || a==2) return memo[a]=1;
return memo[a]=(f(a-1)+f(a-2))%10009;
}
int main()
{
int a;
scanf("%d", &a);
printf("%d",f(a));
}
s(1,1) => s(1,0) + s(0,1)
*/
/*#include<stdio.h>
int memo[15][15]={};
int SuperSum (int a, int b)
{
if(memo[a][b]!=0) return memo[a][b];
if(a==0) return memo[a][b]=b;
if(b==0) return memo[a][b]=0;
return memo[a][b]=SuperSum(a,b-1)+SuperSum(a-1,b);
}
int main()
{
int a,b;
while( scanf("%d %d", &a, &b) != EOF )
printf("%d\n", SuperSum(a, b));
}
*/
/*#include<stdio.h>
int memo[51][51]={};
int f(int a,int b)
{
if(memo[a][b]!=0) return memo[a][b];
if(a==0 || b==0) return 1;
return memo[a][b]=(f(a,b-1)+f(a-1,b))%100000000;
}
int main()
{
int a,b;
scanf("%d %d", &a,&b);
printf("%d", f(a-1,b-1));
}
*/
/*#include<stdio.h>
int memo[100001]={};
int f(int a)
{
if(memo[a]!=0) return memo[a];
if(a==1) return memo[a]=1;
if(a==2) return memo[a]=2;
if(a==3) return memo[a]=4;
return memo[a]=(f(a-1)+f(a-2)+f(a-3))%1000;
}
int main()
{
int a;
scanf("%d", &a);
printf("%d", f(a));
return 0;
}
*/