//#include<stdio.h>
//
//int SuperSum(int k, int n)
//{
//
//
//
//
//
//}
//
//int main()
//{
// int i, n, k;
//
// while( scanf("%d %d", &k, &n) != EOF )
// printf("%d\n", SuperSum(k, n));
//}
//#include<stdio.h>
//
//int memo[12000] = {0};
//
//int fibo(int k) {
// if(k==1 || k==2) {
// return memo[k];
// }
// if(memo[k]!=0) {
// return memo[k]%10009;
// }
//
// return memo[k] = ((fibo(k-1)%10009)+(fibo(k-2)%10009))%10009;
//}
//
//int main() {
// int n;
// scanf("%d", &n);
//
// memo[1] = memo[2] = 1;
//
// printf("%d", fibo(n)%10009);
//}
//
//