Fibonacci Sequence

The Fibonacci sequence is defined as follows: the first and second numbers of the sequence are both 1, and each subsequent number is the sum of the previous two. In mathematical terms, the sequence is defined by:

\(F(1)=1,\ F(2)=1,\ \forall n\geq3,\ F(n)=F(n-1)+F(n-2)\).

Given a positive integer \(a\), your task is to compute the \(a\)-th number in this Fibonacci sequence.

inputFormat

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

outputFormat

Output the \(a\)-th Fibonacci number.

sample

1

1