Sequence Computation with the Golden Ratio

Wolfycz is fascinated with sequences and the golden ratio. One day, he defined a sequence using the formula: $$A_i = \lceil \left(\frac{\sqrt{5}+1}{2}\right)^i \rceil.$$ However, Wolfycz does not know the value of \(A_n\). Your task is to compute \(A_n\) given a positive integer \(n\).

Note: Be cautious about the impact of constant factors on the efficiency of your program.

inputFormat

The input consists of a single line containing one positive integer \(n\) (\(1 \le n \le 10^5\)).

outputFormat

Output the value of \(A_n\) computed by the formula $$A_n = \lceil\left(\frac{\sqrt{5}+1}{2}\right)^n\rceil.$$

sample

1

2