using System;

public class Program

{

    public static void Main()

    {

        //

        // 0 1 1 2 3 5 8

        int result = fibDP(4);// fib(4);

        Console.WriteLine(result);

    }

    static int fib(int n)

    {

        if(n == 0 || n == 1)

        {

            return 1;

        }

        return fib(n-1) + fib(n-2);

    }

    static int fibDP(int n)

    {       

        int[] table = new int[n+1];

        table[0] = 1;

        table[1] = 1;

        int i;

        for(i=2; i <= n; ++i)

        {

            table[i%3] = table[(i-1)%3] + table[(i-2)%3];

        }

        /*

        0 1 2

        3 4

        */

        //Console.WriteLine("0, "+ string.Join(", ", table));

        return table[n%3];

    }

}