/*
#include<stdio.h>
int memo[203]={};
int fib(int n)
{
if(n==1||n==2)
return 1;
if(memo[n]==0)
{
memo[n]=fib(n-1)+fib(n-2);
return memo[n]%10009;
}
else
{
return memo[n]%10009;
}
}
int main()
{
int n;
scanf("%d", &n);
printf("%d",fib(n));
return 0;
}
*/
/*
#include<stdio.h>
int memo[100001]={};
int fib(int n)
{
if(n==1||n==2)
return memo[n]=n;
if(memo[n]==0)
{
memo[n]=fib(n-1)+fib(n-2);
return memo[n]%100000007;
}
else
{
return memo[n]%100000007;
}
}
int main()
{
int n;
scanf("%d", &n);
printf("%d", fib(n));
}
*/
/*
#include<stdio.h>
void rec(int n)
{
if(n==0)return;
rec(n-1);
}
int main()
{
int n, r;
scanf("%d", &n);
printf("%d", rec(n));
}
*/
/*
#include<stdio.h>
int rec(int n, int f)
{
if(n==f) return f;
return n * rec(n-1, f);
}
int main()
{
int n, r, k;
int rn, rm, x, y;
scanf("%d %d", &n, &r);
k = n-r;
if(k>r) x = k;
else x = r;
if(k<r) y = k;
else y = r;
rm = rec(y,1);
rn = rec(n, x+1);
printf("%d", rn/rm);
}
*/