e-olymp
Задачі

Зоопарк

Зоопарк

prb157new

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

Наглядач спробував було порахувати сам, але збився з рахунку десь в районі бегемотів. І цілком очевидно, що без вашої допомоги йому не справитись!

Вхідні дані

Кількість кліток n (2n100) у зоопарку.

Вихідні дані

Виведіть кількість способів поселити Славу та Юру в різні клітки так, щоб ці клітки не були сусідніми.

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
3
Вихідні дані #1
2
Вхідні дані #2
4
Вихідні дані #2
6