Fibonacci String Length

Given a positive integer n, compute the length of the Fibonacci string of order n. The Fibonacci string is defined recursively as follows:

$$L(1)=1,\quad L(2)=1,\quad \text{and}\quad L(n)=L(n-1)+L(n-2)\quad \text{for } n\geq3.$$

For example, if n is 3, then L(3)=2; if n is 5, then L(5)=5.

inputFormat

The input consists of a single integer n (1 ≤ n ≤ 10⁵) provided via standard input.

outputFormat

Output the Fibonacci string length corresponding to the given integer n on standard output.

1

1