Explosiveness 2#5065

Explosiveness 2

1 second

64 megabytes

Easy

In the processing of radioactive materials, two types of waste are produced: highly hazardous (type A) and safe (type B). Both types are stored in identical containers, which are then stacked vertically. A stack becomes explosive if it includes more than one consecutive container of type A. Given a total of $N$ containers, calculate the number of possible configurations for safe stacks.

Input

The first line contains the number $N$ ( $1 \leq N \leq 1000$ 1 \leq N \leq 1000).

Output

Output a single integer representing the number of safe stack configurations.

Examples

Example 1

Loading

1 \leq N \leq 1000