Fibonacci Numbers 4

The Fibonacci numbers start with 0 and 1. The 0th Fibonacci number is 0, the 1st Fibonacci number is 1, and from index 2 on each number is the sum of the two before it. As a formula, $F_n = F_{n-1} + F_{n-2}$ for $n \ge 2$.

Written out through n = 17, the Fibonacci numbers are as follows.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

Given n, write a program that computes the nth Fibonacci number.

The first line contains n. n is 0 or a natural number no greater than 10,000.

Print the nth Fibonacci number on the first line. The value grows too large for a 64-bit integer, so compute it with arbitrary-precision arithmetic.