#include <cstdio>
#include <cassert>
#include <cstring>

static const unsigned g_k_MAXN = 10000;
static unsigned long fib[g_k_MAXN];

static unsigned long  fibonacci(unsigned n)
{
 if (fib[n] > 0) return fib[n];
 if (n == 1) return fib[1] = 1;
 if (n == 2) return fib[2] = 1;
 return fib[n] = fibonacci(n-1) + fibonacci(n-2);
}

int main()
{
 unsigned n;
 printf("please input unsigned n: ");
 scanf("%d", &n);
 assert( (n > 0) && (n <= g_k_MAXN) );

 memset(fib, 0, sizeof(fib));
 printf("the nth element of fibonacci is: %lu\n", fibonacci(n));

 return 0;
}