Олимпиадный тренинг

Задача 27084. Pet shop-2


Задача

Темы:
In a pet store, you need to arrange cages with cats and dogs in one row. N cells are placed in a row, while there is one restriction: you cannot put three cells in a row with animals of the same species (otherwise they will fight). It is assumed that the store has an unlimited number of cages with cats and dogs. 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.

Enter Output
5 16