import java.util.Scanner;

/**
 * fibonacci
 */
public class fibonacci {
    public static long[] fibonacciCache;
    public static void main(String[] args) {
        System.out.println("Let's try to get back on the horse!");
        Scanner sc = new Scanner(System.in);
        System.out.println("Please enter the number you wanna search: ");
        int fib = sc.nextInt();
        sc.close();
        fibonacciCache = new long[1+fib];
        for (int i = 0; i <= fib; i++) {
            System.out.println(i + "==> " + fibonacciNum(i));   
        }
    }

    public static long fibonacciNum(int x){
        if (x <= 1){
            return x;
        }
        if (fibonacciCache[x] != 0){
            return fibonacciCache[x];
        }
        long nthFib = (fibonacciNum(x-1)+(fibonacciNum(x-2)));
        fibonacciCache[x] = nthFib;
        return nthFib;
    }
}