Fibonacci Dish Price

After calculating the bill, Yue Luo Wu Qi exclaimed, "You tricked me!" When Ai Yu Chou the Great asked for the price of the nth dish, Yue Luo Wu Qi scribbled down a mysterious formula:

$$F_n=\dfrac{\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n}{\sqrt{5}}$$

Since Ai Yu Chou had learned programming, he quickly computed the value of F_n within one minute. Yue Luo Wu Qi was astonished by his speed. Can you follow in Ai Yu Chou's footsteps and compute the value of F_n?

inputFormat

The input consists of a single positive integer n (1 ≤ n ≤ 90), which represents the dish number.

outputFormat

Output the value of F_n, defined by the formula:

$$F_n=\dfrac{\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n}{\sqrt{5}}$$

Note: The value is the nth Fibonacci number (with F(1)=1 and F(2)=1).

sample

1

1