/*
#include <stdio.h>
int f(int n)
{
if(n==0)
{
return;
}
if(n%2==0)
{f(n/2);
printf("0");
}
else
{f(n/2);
printf("1");
}
}
int main()
{
int n;
scanf("%d",&n);
if(n==0)
{
printf("0");
}
f(n);
}
*/
/*
#include <stdio.h>
void f(int n,int k)
{
if(n==0)
{
return;
}
f(n/k,k);
if(n%k>9&&n%k<=16)
{
printf("%c",n%k+55);
}
else
{
printf("%d",n%k);
}
}
int main()
{
int n,k;
scanf("%d %d",&n, &k);
f(n,k);
}
*/
/*
#include <stdio.h>
int f(int n)
{
if(n==1||n==2)
{
return 1;
}
return f(n-1) + f(n-2);
}
int main()
{
int n;
scanf("%d",&n);
printf("%d",f(n));
}
*/
/*
#include <stdio.h>
int str[201] = {};
int f(int n)
{
if(str[n]>0)
{
return str[n];
}
if(n==1||n==2)
{
str[n] = 1;
}
else
{
str[n] = ( f(n-1) + f(n-2) )%10009;
}
return str[n];
}
int main()
{
int n;
scanf("%d",&n);
printf("%d",f(n));
}
*/
/*
#include <stdio.h>
int str[51][51] = {};
int f(int r,int c)
{
if(str[r][c]>0)
{
return str[r][c];
}
if(r==1||c==1)
{
str[r][c] = 1;
}
else
{
str[r][c] = (f(r-1,c) + f(r,c-1))%100000000;
}
return str[r][c];
}
int main()
{
int r,c;
scanf("%d %d",&r,&c);
printf("%d",f(r,c));
}
*/