In a pet store, you need to arrange cages with animals in one row. N cells are placed in a row, while there is one restriction: you cannot put two cells with dogs next to each other (otherwise they will fight). It is assumed that the store has an unlimited number of cages with different animals. Determine how many safe ways you can arrange N cells in a row.
Input
The input string contains one natural number – number of cells in a row N .
Output
The program should output the number of safe ways to arrange N cells in a row.