Dynamic Programming Fibonacci

Given an integer n, compute the nth Fibonacci number using a dynamic programming approach. The Fibonacci sequence is defined as:

\(F_0 = 0, \quad F_1 = 1, \quad F_n = F_{n-1} + F_{n-2} \quad \text{for } n \ge 2\)

Your program should read the input from stdin and output the result to stdout. The algorithm should be efficient enough to compute values up to n = 100.

inputFormat

The input consists of a single integer n in one line.

outputFormat

Output the nth Fibonacci number in one line.

0

0