//#include <stdio.h>
//
//int rec(int n)
//{
// if(n==1)
// {
// printf("%d\n", 1);
// return;
// }
//
// if(n%2==0)
// {
// rec(n/2);
// printf("%d\n", n);
// }
// else
// {
// rec(3*n+1);
// printf("%d\n", n);
// }
//}
//
//int main()
//{
// int n;
//
// scanf("%d", &n);
//
// rec(n);
//
// return 0;
//}
//#include <stdio.h>
//int star(int a)
//{
// if(a==0)
// {
// printf("\n");
// return;
// }
// else
// {
// printf("*");
// star(a-1);
// }
//}
//
//int rec(int n)
//{
// if(n==1)
// {
// printf("*\n");
// return;
// }
// else
// {
// rec(n-1);
// star(n);
// }
//
//}
//
//int main()
//{
// int n;
//
// scanf("%d",&n);
//
// rec(n);
//
// return 0;
//}
//#include <stdio.h>
//
//int rec(int n)
//{
// if(n==0)
// {
//
// return;
// }
// else
// {
// rec(n/2);
// printf("%d",n%2);
// }
//}
//
//int main()
//{
// int n;
//
// scanf("%d",&n);
//
// rec(n);
//
// if(n==0)
// {
// printf("0");
// }
//
// return 0;
//}
//#include <stdio.h>
//
//int memo[250]= {};
//
//int rec(int n)
//{
// if(n<=2)
// {
// return 1;
// }
// else
// {
// if(memo[n]!=0)
// {
// return memo[n]%10009;
// }
// else
// {
// memo[n]=rec(n-1)+rec(n-2);
// return memo[n]%10009;
// }
// }
//}
//
//int main()
//{
//
// int n;
//
// scanf("%d", &n);
//
// printf("%d",rec(n));
//
// return 0;
//}
//#include <stdio.h>
//
//int a=1;
//int b=1;
//int rec(int n, int r)
//{
//
// if(r==0)
// {
// printf("%d", a/b);
// return a;
// }
// else
// {
// a=a*n;
// b=b*r;
// return rec(n-1,r-1);
// }
//}
//
//int main()
//{
// int n, r;
//
// scanf("%d %d", &n, &r);
//
// if(r>n/2)
// {
// r=n-r;
// }
//
// if(r==0)
// {
// printf("0");
// }
// else
// {
// rec(n, r);
// }
//
// return 0;
//}