Assignment

Write a program that asks the user for a number, and then prints the Fibonacci number at that index.

What are Fibonacci numbers?

The Fibonacci numbers form a sequence of numbers where each number is the sum of the previous two. It usually starts with 1 and 1, which makes the third number 2 (1+1=2). The first 20 Fibonacci numbers are:

Index Fibonacci number Why?
1 1
2 1
3 2 1 + 1 = 2
4 3 1 + 2 = 3
5 5 2 + 3 = 5
6 8 3 + 5 = 8
7 13 5 + 8 = 13
8 21 8 + 13 = 21
9 34 13 + 21 = 34
10 55 21 + 34 = 55
11 89 34 + 55 = 89
12 144 55 + 89 = 144
13 233 89 + 144 = 233
14 377 144 + 233 = 377
15 610 233 + 377 = 610
16 987 377 + 610 = 987
17 1597 610 + 987 = 1597
18 2584 987 + 1597 = 2584
19 4181 1597 + 2584 = 4181
20 6765 2584 + 4181 = 6765

(PS: The first two numbers can be chosen freely and decide what the entire sequence will look like. In this assignment we will just condisder the standard 1 and 1.)



Examples

Example 1

Input

6

Output

Fibonacci number 6 is: 8.
Example 2

Input

10

Output

Fibonacci number 10 is: 55.
Example 3

Input

17

Output

Fibonacci number 17 is: 1597.
Example 4

Input

20

Output

Fibonacci number 20 is: 6765.