Danger of explosion

On one of the secret plants is processed radioactive materials, which resulted in radioactive waste in two types: type A (very dangerous) and type B (non-hazardous). All waste is packed in special rectangular containers of equal size, after which the containers are stacked in a pile on top of each other to save. A stack is explosive if it side by side two boxes of waste by type A is required to write a program that counts the number of possible formation of non-explosive stack of a given total number of containers, N.

Input

The input file contains a single integer N (1 ≤ N ≤ 100).

Output

The output file must take the required number of options.

Examples