/*#include<stdio.h>
long long int f(long long int x,long long int y)
{
if(x==y+1)
{
return y+1;
}
return f(x-1,y)*x;
}
int main()
{
int x;
int y;
scanf("%d %d",&x,&y);
if(y>x-y)
{
printf("%d",f(x,y)/f(x-y,0));
}
else
{
printf("%d",f(x,x-y)/f(y,0));
}
}*/
/*
#include<stdio.h>
int map[21]={0};
int f(int x)
{
if(x==1)
{
return 1;
}
if(x==2)
{
return 2;
}
if(map[x]!=0)
{
return map[x];
}
map[x]=f(x-1)+f(x-2);
return map[x];
}
int main()
{
int x;
scanf("%d",&x);
printf("%d",f(x));
}
*/
/*
#include<stdio.h>
int map[10000]={0};
int f(int x)
{
if(x==1 || x==2)
{
return x;
}
if(map[x] != 0)
{
return map[x];
}
map[x]=(f(x-1)+f(x-2))%100000007;
return map[x];
}
int main()
{
int x;
int y;
scanf("%d",&x);
printf("%d",f(x));
}
*/
/*
#include<stdio.h>
int map[10000]={0};
int f(int x)
{
if(x==1)
{
return 2;
}
return f(x-1)*2;
}
int main()
{
int x;
scanf("%d",&x);
if(x%3==0) printf("%d",f(x/3)%100000007);
else printf("0");
}
*/