/*#include <stdio.h>
long long int f(int n,int k)
{
if(k==0)
return 1;
long long int x = f(n,k/2);
long long int y = x*x;
if(k%2==1) y*=n;
return y;
// if(k==0)
// {
// return 1;
// }
// return f(n,k-1)*n;
}
int main()
{
int n,k;
scanf("%d %d",&n,&k);
if(n==0)
printf("0");
else if(n==1||n==-1)
{
if(n==-1&&k%2==1)
printf("-1");
else
printf("1");
}
else
printf("%lld",f(n,k));
}*/
//메모이제이션 memoization
//중복으로 계산하지 않도록 계산했던 값을 메모해 놓고 가져와서 사용
/*
#include <stdio.h>
int a[201]={};
int f(int n)
{
if(a[n]!=0)
return a[n];
if(n<=2)
{
a[n]=1;
return 1;
}
a[n] = (f(n-1)+f(n-2))%10009;
return a[n];
}
int main()
{
int n;
scanf("%d",&n);
printf("%d",f(n));
}
#include <stdio.h>
int a[51][51]={};
int pas(int r,int c)
{
if(a[r][c]!=0)
return a[r][c];
if(r==1||c==1)
{
a[r][c]=1;
return 1;
}
a[r][c]=(pas(r,c-1)+pas(r-1,c))%100000000;
return a[r][c];
}
int main()
{
int r,c;
scanf("%d %d",&r,&c);
printf("%d",pas(r,c));
}*/
//간단한 문제, 문자열 -> python
//복잡한데 시간을 줄여야 하는 문제 -> c