#include <stdio.h>
#include <stdlib.h>

int fib(int n);

int main() {
	int n;

	printf("N? (max: 46) "); scanf("%d", &n);

	printf("%d %d\n", n, fib(n));
	return 0;
}

int fib(int n) {
	if (n == 0 || n == 1) return n;

	int i;
	int * tab = malloc(sizeof(int) * (n + 1));

	tab[0] = 0, tab[1] = 1;

	for(i = 2; i < n + 1; i++) {
		tab[i] = tab[i - 1] + tab[i - 2];
	}

	return tab[n];
}