import java.util.*;

public class fib {
    public static void main(String[] Args) {
        int n = 47;
        memo = new long[n + 1];
        Arrays.fill(memo, SENT);
        System.out.println(fibBotUp(n));
    }
    
    public static long[] memo;
    public static long SENT = -1;
    public static long fibRec(int i) {
        if (i == 0 || i == 1) 
            return i;
        /*if (memo[i] != SENT)
            return memo[i];
        */
        memo[i] = fibRec(i - 1) + fibRec(i - 2);
        return memo[i];
    }
    
    public static long fibBotUp(int i) {
        // Compute base cases
        memo[0] = 0;
        memo[1] = 1;
        
        // Find the next state
        for (int j = 2; j <= i; j++) {
            memo[j] = memo[j-1] + memo[j-2];
        }
        
        return memo[i];
    }
}