Задача. Найдите количество вариантов локализации вирусов в системе N последовательно-соединённых городов, с учётом того, что вирусы могут распространя

Задача 3. «Эпидемия»
В придуманной стране города располагаются полукругом вокруг пустыни и соединены
одной дорогой (не циклично). А в пустыне этой находится научно-исследовательская зона, в
которой изучают, в том числе, различные вирусные заболевания. Но однажды из пустыни
сбежало два подопытных зубра, каждый из которых был заражён отдельной
экспериментальной болезнью, и направились к основной дороге. Вирусы эти, хоть и были
очень заразными, не передавались носителю альтернативного штамма. Правительство тут же
дало отделу «К» задачу проанализировать возможность заражения и варианты карантина с
учётом того, что зубры явно двигались в направлениях разных городов и уже наверняка их
достигли. Решение было принято такое: в случае обнаружения заражения в городе, в нём
объявляется карантин, если в соседнем городе обнаружено заболевание тем же штаммом
вируса, карантинная зона расширяется и на этот город. Но, на всякий случай, решили не
объединять карантинные зоны разных штаммов вируса.
Задача. Найдите количество вариантов локализации вирусов в системе N
последовательно-соединённых городов, с учётом того, что вирусы могут распространяться
только в соседние города, соединённые главной дорогой, и два города (неизвестно, какие)
изначально заражены разными штаммами вируса.
Потоки. Входной поток содержит одно натуральное число N. Выходной поток должен
содержать одно натуральное число.
Пример
Входной поток:
3
Выходной поток:
5

0