//#include<stdio.h>
//
//int rec(int n)
//{
// if(n==1)return 1;
// return n+rec(n-1);
//}
//
//int main()
//{
// int n;
//
// scanf("%d",&n);
// printf("%d",rec(n));
//}
//#include<stdio.h>
//
//int rec(int n)
//{
// if(n==1)return 1;
// return n*rec(n-1);
//}
//
//int main()
//{
// int n;
//
// scanf("%d",&n);
// printf("%d",rec(n));
//
// return 0;
//}
//#include<stdio.h>
//
//int rec(int n)
//{
// if(n==1 || n==2)return 1;
// return rec(n-2)+rec(n-1);
//}
//
//int main(){
//
// int n;
//
// scanf("%d",&n);
// printf("%d",rec(n));
// return 0;
// }
/*#include<stdio.h>
long long int rec(int n)
{
if(n<=2)return 1;
return (rec(n-1)+rec(n-2))%10009;
}
int main()
{
int n;
scanf("%d",&n);
printf("%lld",rec(n));
return 0;
}*/
//#include<stdio.h>
//
//void rec(int n)
//{
// if(n==1)
// {
// printf("%d\n",n);
// return;
// }
// if(n%2==0)
// {
// printf("%d\n",n);
// rec(n/2);
// }
// else if(n%2==1)
// {
// printf("%d\n",n);
// rec(n*3+1);
// }
//}
//
//int main()
//{
// int n;
//
// scanf("%d",&n);
// rec(n);
//}
/*#include<stdio.h>
int rec(int k, int n)
{
}
int main()
{
int i,k,n;
for(i=0; i<4; i++)
{
scanf("%d %d",&k,&n);
}
for(i=0; i<4; i++)
{
printf("%d\n",rec(k,n));
}
return 0;
}*/