eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Зоопарк

Зоопарк

Лимит времени 1 секунда
Лимит использования памяти 128 MiB
prb157new

В зоопарке n клеток выстроены в ряд. В зоопарке, кроме прочих обитателей, живут две мартышки, Слава и Юра. Слава и Юра всегда были большими друзьями и сидели в соседних клетках, но теперь они поссорились и больше не хотят видеть друг друга. Смотритель уже собрался переселить их в соответствии с их желанием, однако возникла проблема. Слава и Юра - очень образованные мартышки (каждый из них закончил аж по восемь классов!), и они непременно хотят знать, сколько всего существует способов расселить их так, чтобы их клетки не были соседними, и уж конечно их клетки должны быть различными. Можно считать, что все n клеток доступны, остальные обитатели зоопарка готовы переехать куда угодно.

Смотритель попытался было сосчитать сам, но сбился со счёта где-то в районе бегемотов. И совершенно определённо, без вашей помощи ему не справиться!

Входные данные

Количество клеток n (2n100) в зоопарке.

Выходные данные

Выведите количество способов поселить Славу и Юру в разные клетки так, чтобы эти клетки не были соседними.

Пример

Входные данные #1
3
Выходные данные #1
2
Входные данные #2
4
Выходные данные #2
6