/*
#include <stdio.h>
void star(int n) //*을 n개 출력 재귀함수
{
if(n==0) return ;
star(n-1);
printf("*");
}
void f(int n) //1~ n출력하는 재귀함수
{
if(n==0) return;
f(n-1);
star(n);printf("\n");
}
int main()
{
int n;
scanf("%d",&n);
f(n);
return 0;
}
*/
/*
#include <stdio.h>
int n;
int f(int n)
{
if(n==0) return;
printf("%d\n",n);
f(n-1);
}
int main()
{
scanf("%d",&n);
f(n);
return 0;
}
*/
/*
#include <stdio.h>
void f(int n)
{
if(n==0) return ;
f(n/2);
printf("%d",n%2);
}
int main()
{
int n;
scanf("%d",&n);
if(n==0) printf("0");
f(n);
return 0;
}
*/
/*
#include <stdio.h>
int memo[201]={};
int f(int n)
{
if(memo[n]!=0) return memo[n];
if(n==1) return memo[n]=1;
if(n==2) return memo[n]=1;
return memo[n] = (f(n-1)+f(n-2))%10009;
}
int main()
{
int n;
scanf("%d",&n);
printf("%d",f(n));
return 0;
}
*/
/*
#include <stdio.h>
int memo[51][51]={};
int f(int r,int c)
{
if(memo[r][c]!=0) return memo[r][c];
if(r==1||c==1) return 1;
return memo[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));
return 0;
}
f(1) =?1
f(2) =2
f(3) 4
f(4) 7
f(5) 13
f(n)= ??
*/
/*
#include <stdio.h>
int memo[100001]={};
int f(int n)
{
if(memo[n]!=0) return memo[n];
if(n==1) return memo[n]=1;
if(n==2) return memo[n]=2;
if(n==3) return memo[n]=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>
long long int f(int n)
{
long long int fac=1;
}