/*
#include <stdio.h>
void s(int b)
{
printf("*");
if(b>1)
{
s(b-1);
}
else
return 0;
}
void f(int n)
{
if(n>0)
{
s(n);
printf("\n");
f(n-1);
}
else
return 0;
}
int main()
{
int a;
scanf("%d",&a);
f(a);
}
*/
/*
#include <stdio.h>
int f(int n)
{
if(n==1)
{
return 1;
}
if(n%2==1)
{
return 1 + f(3*n+1);
}
else
{
return 1 + f(n/2);
}
}
int main()
{
int n;
scanf("%d", &n);
printf("%d",f(n));
return 0;
}
f(5)
f(4) -> f(3) + f(2)
f(3)
*/
/*
#include <stdio.h>
int a[201]={0, 1, 1};
int f(int k)
{
if(a[k]!=0) return a[k];
if(k<=2) return 1;
else return a[k] = (f(k-1)+f(k-2))%10009;
}
int main()
{
int n;
scanf("%d", &n);
printf("%d",f(n));
return 0;
}
*/
//3702
/*
#include <stdio.h>
int a[51][51]={};
int f(int r, int c)
{
if(r==1||c==1)
{
return 1;
}
if(a[r][c]!=0)
{
return a[r][c];
}
return a[r][c]=(f(r-1, c)+f(r, c-1))%100000000;
}
int main()
{
int r, c;
scanf("%d %d", &r, &c);
printf("%d", f(r, c));
}
*/