Fibonacci with Memoization

Calculate the nth Fibonacci number using memoization for efficiency. Fibonacci sequence: F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2) Naive recursion is O(2^n). With memoization, it's O(n). Example: n=10 → F(10)=55

Input

A single integer n.

Output

The nth Fibonacci number.

Sample

10

Expected

55