Fibonacci Numbers 4

Interview

Time limit1sMemory limit256 MB

Summary

Compute the nth Fibonacci number for n up to 10000 using arbitrary-precision arithmetic.

Level: Easy3 of 10
Topics: Dynamic programming, Implementation
Solved: No attempts yet

Problem

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.

Input

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

Output

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.

Examples6

Example 1
Input
```
10
```
Expected output
```
55
```
Example 2
Input
```
0
```
Expected output
```
0
```
Example 3
Input
```
1
```
Expected output
```
1
```
Example 4
Input
```
2
```
Expected output
```
1
```
Example 5
Input
```
3
```
Expected output
```
2
```
Example 6
Input
```
17
```
Expected output
```
1597
```