The Fibonacci sequence in this problem is indexed from \(1\) and defined by

• \(F_1 = 0\),
• \(F_2 = 1\),
• \(F_n = F_{n-1} + F_{n-2}\) for \(n \ge 3\).

Given \(n\), compute \(F_n\).

Input

One line containing \(n\).

The input satisfies:

• \(1 \le n \le 45\)

Output

Print \(F_n\).

Example

Input

6

Output

5