/*
#include <stdio.h>
int memo[201]={};
int rec(int n)
{
if(memo[n]!=0)
{
return memo[n];
}
if(n==1||n==2)
{
memo[n]=1;
return memo[n];
}
return memo[n]=(rec(n-1)+rec(n-2))%10009;
}
int main()
{
int n;
scanf("%d",&n);
printf("%d",rec(n)%10009);
return 0;
}
*/
/*
#include <stdio.h>
int memo[51][51]={};
int rec(int r,int c)
{
if(memo[r][c]!=0)
{
return memo[r][c];
}
if(r==1||c==1)
{
return memo[r][c]=1;
}
return memo[r][c]=(rec(r-1,c)+rec(r,c-1))%100000000;
}
int main()
{
int r,c;
scanf("%d %d",&r,&c);
printf("%d",rec(r,c));
}
*/
#include <stdio.h>
int rec(int r,int c)
{
}