public class FibonacciImproved {
    // $F_{93}$ does not fit into a long
    static long[] lookup = new long[93];
    
    public static long fib(int n) {
        if (lookup[n] > 0) return lookup[n];
        
        if (n > 1) {
            lookup[n] = fib(n-1)+fib(n-2);
            return lookup[n];
        } else
            return n;
    }
    public static void main(String args[]) {
        System.out.println(fib(50));
    }
}