The following languages are only available languages for the problems from the contest

Unknown Language Round #2:

- Io-2008-01-07 (Win32)

No tag edit access

G. Fibonacci army

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputKing Cambyses loves Fibonacci numbers. He has several armies. Today he wants to make a new army for himself and he wants the number of men in this army to be the *n*-th Fibonacci number.

Given *n* you should find *n*-th Fibonacci number. The set of Fibonacci numbers start with *f*_{0} = *f*_{1} = 1 and for each *i* ≥ 2, *f*_{i} = *f*_{i - 1} + *f*_{i - 2}.

Input

Input contains a single integer *n* (1 ≤ *n* ≤ 20).

Output

Write a single integer. The *n*-th Fibonacci number.

Examples

Input

2

Output

2

Input

1

Output

1

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/18/2017 03:18:51 (p1).

Desktop version, switch to mobile version.

User lists

Name |
---|