import java.util.HashMap;
import java.util.Map;

public class Fibonacci {
	private static Map<Integer, Long> memoizationMap = new HashMap<>();

	public static long calcFibo(int n) {
    
    //SECOND
		if (n <= 1) {
			return n;
		}

		if (memoizationMap.containsKey(n)) {
			return memoizationMap.get(n);
		}

		long fiboValue = calcFibo(n - 1) + calcFibo(n - 2);
		memoizationMap.put(n, fiboValue);

		return fiboValue;
	}
}