//#include <stdio.h>
//int a(int n)
//{
// if(n==1 || n==2)
// return 1;
// else
// return a(n-1)+a(n-2);
//}
//
//int main()
//{
// int n;
// scanf("%d", &n);
// printf("%d",a(n));
//}
/*
#include <stdio.h>
int a(int r, int c)
{
if(r==1||c==1)
{
return 1;
}
return a(r-1, c)+a(r, c-1);
}
int main()
{
int r, c;
scanf("%d %d", &r, &c);
printf("%d", a(r, c)%100000000);
}
*/
//#include <stdio.h>
//void star(int n)
//{
// if(n==0)
// {
// return;
// }
// printf("*");
// star(n-1);
//}
//
//
//int a(int n)
//{
// if(n==0)
// {
// return;
// }
// a(n-1);
// star(n);
// printf("\n");
// //printf("%d\n", n);
//}
//
//
//int main()
//{
// int n;
// scanf("%d", &n);
// a(n);
//
//}
//#include <stdio.h>
//
//int n, k, d[1010];
//int lower_bound(int k)
//{
// for(int i=1;i<=n;i++)
// {
// if(d[i]>=k)
// {
// return i;
// }
// }
//
// return n+1;
//
//}
//int main()
//{
// scanf("%d", &n);
//
// for(int i=1; i<=n; i++)
// scanf("%d", &d[i]);
//
// scanf("%d", &k);
//
// printf("%d\n", lower_bound(k));
//}
//#include <stdio.h>
//
//int n, r;
//
//int a(int n, int r)
//{
// if(r==1||r==n)
// {
// return 1;
// }
// return a(n-1, r)+a(n-1, r-1);
//}
//
//int main()
//{
//
// scanf("%d %d", &n, &r);
// printf("%d", a(n, r));
//}