/*
#include <stdio.h>
int f(int a)
{
if(a==1)
{
return 1;
}
return a+f(a-1);
}
int main()
{
int a;
scanf("%d", &a);
printf("%d", f(a));
return 0;
}
#include <stdio.h>
int f(long long int a)
{
if(a<=9)
{
return a;
}
return a%10+f(a/10);
}
int main()
{
long long int a;
scanf("%lld", &a);
printf("%d", f(a));
return 0;
}
#include <stdio.h>
void f(int a)
{
if(a==1||a==0)
{
printf("%d", a);
}
else
{
f(a/2);
printf("%d", a%2);
}
}
int main()
{
int a;
scanf("%d", &a);
f(a);
}
#include <stdio.h>
void f(int a,int b)
{
if(a<b)
{
if(a<10)
{
printf("%d", a);
}
else
{
printf("%c",a+55);
}
}
else
{
f(a/b,b);
if(a%b<10)
{
printf("%d", a%b);
}
else
{
printf("%c",a%b+55);
}
}
}
int main()
{
int a, b;
scanf("%d %d", &a, &b);
f(a, b);
return 0;
}
#include <stdio.h>
int arr[205]={};
int f(int a)
{
if(a==1||a==2)
{
return 1;
}
else if(arr[a]!=0)
{
return arr[a];
}
else
{
return arr[a]=(f(a-2)+f(a-1))%10009;
}
}
int main()
{
int a;
scanf("%d", &a);
printf("%d", f(a));
return 0;
}
#include <stdio.h>
int arr[55][55]={};
int f(int r, int c)
{
if(c==1 || r==1)
{
return 1;
}
if(arr[r][c]!=0)
{
return arr[r][c];
}
return arr[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));
}
*/