/*
#include <stdio.h>
void f(int n)
{
if(n==0) {
printf("0");
return;
}
if(n>1) f(n/2);
printf("%d",n%2);
}
int main()
{
int n;
scanf("%d",&n);
f(n);
return 0;
}
*/
/*#include <stdio.h>
int n,k;
void f(int n,int k)
{
if (n==0) return ;
f(n/k,k);
if(n%k<10) printf("%d",n%k);
else printf("%c",n%k+55);
}
//10 65 'A'
//11 66 'B'
int main()
{
int n,k;
scanf("%d %d",&n,&k);
f(n,k);
return 0;
}
*/
/*
#include <stdio.h>
int flag;
void f(int n)
{
if (n==0) return ;
if(n%10!=0) flag=1;
if(flag==1) printf("%d",n%10);
f(n/10);
}
int main()
{
int n;
scanf("%d",&n);
flag=0;
f(n);
if (n==0)
{
printf("0");
}
return 0;
}
*/
/*
#include <stdio.h>
void f(int n, int zeroPoint)
{
if (n==0) return ;
if(n%10!=0) zeroPoint=0;
if(zeroPoint==0) printf("%d",n%10);
f(n/10,zeroPoint);
}
int main()
{
int n;
scanf("%d",&n);
f(n,1);
if (n==0)
{
printf("0");
}
return 0;
}
#include <stdio.h>
int memo[201]={};
int f(int n)
{
if(memo[n]!=0) return memo[n];
if (n==1 || n==2){
return 1;
}
return memo[n] = (f(n-1)+f(n-2))%10009;
}
int main()
{
int n;
scanf("%d",&n);
printf("%d",f(n));
return 0;
}
f(1)=1
f(2)=2
f(3)=4
f(4)=7
f(5)=13
f(6)=24
44
81
*/
/*
#include <stdio.h>
int memo[100001]={};
int f(int n)
{
if (memo[n]!=0) return memo[n];
if (n==1) {return 1;}
if (n==2){return 2;}
if (n==3) {return 4;}
return memo[n] = (f(n-1)+f(n-2)+f(n-3))%1000;
}
int main()
{
int n;
scanf("%d",&n);
printf("%d",f(n));
return 0;
}
*/
/*
#include <stdio.h> supersum 집에서 다시 해보기
int memo [1000][1000]={};
int f(int k, int n)
{
if (memo [k][n]!=0) return memo [k][n];
if (n==0||k==0)
{
return n;
}
return memo [k][n] = f(k,n-1)+f(k-1,n);
}
int main ()
{
int k,n;
while (scanf("%d %d",&k,&n)!=EOF)
printf("%d\n",f(k,n));
return 0;
}
*/
/* segmentation 뜨는 이유 찾아오기
#include <stdio.h>
int memo [100000][100000]={};
long long int rec(int n,int k)
{
if (memo [n][k]!=0) return memo [n][k];
if (n==1||k==0) {
return 1;
}
return memo [n][k]=rec(n,k-1)*n;
}
int main()
{
long long int n,k;
scanf("%d %d",&n,&k);
printf("%lld",rec(n,k));
return 0;
}
*/