Your task this time will be on computing Fibonacci numbers. Sounds easy!... or is it?

The Fibonacci numbers are a sequence of numbers generated by taking the sum of the preceding two values. Formally, the sequence is defined as:

$$\displaystyle f(n) = \begin{cases} 1 & \text{if } n = 1 \\ 1 & \text{if } n = 2 \\ f(n-1) + f(n-2) & \text{if } n \ge 3 \end{cases} $$

Given an integer ~n~ ~(1 \le n \le 50)~, you are to output the ~n^\text{th}~ Fibonacci number.

Note: You may only submit to this problem in Python 3.

Input Specification

The first line of input contains a single integer ~n~.

Output Specification

Output on a single line, the ~n^\text{th}~ Fibonacci number.

Scoring

Your score will be computed based on the length of your source code, the shorter the better. For an ~L~-byte program,

• if ~L \le 43~, you will receive the full ~100~ points.
• if ~44 \le L \le 47~, you will receive ~80-10 \times (L-44)~ points.
• if ~48 \le L~, you will receive ~\lfloor 2^{0.16(80-L)} \rfloor~ points.

Sample Input

8

Sample Output

21