using System;

using System.Collections.Generic;

using System.Numerics;

public class Program

{

    static Dictionary<int, BigInteger> cache = new Dictionary<int, BigInteger>();

    static long counter = 0;

    public static void Main()

    {

        cache = new Dictionary<int, BigInteger>();

        Console.WriteLine("Fibonacci");

        int n = 600;

        for(int i=0; i<=n; i++)

        {

            Console.WriteLine("fib({0}) -> {1}", i, fib2(i));

        }

        Console.WriteLine("Fibonacci counter: {0}", counter);

    }

    public static long fib(int n)

    {

        if(n < 2) { return 1; }

        counter++;

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

    }

    public static BigInteger fib2(int n)

    {

        if(n < 2) { return 1; }

        counter++;

        if(!cache.ContainsKey(n-1)) { cache.Add(n-1, fib2(n-1)); }

        if(!cache.ContainsKey(n-2)) { cache.Add(n-2, fib2(n-2)); }

        return checked(cache[n-1] + cache[n-2]);

    }

}