Коза Ностра

Пока у школьников идет зачет, преподаватели играют в мафию. По кругу сидит $n$ преподавателей. Ведущий должен раздать кому-то из них карты с тузами (тузов любое количество, возможно $0$) — эти преподаватели будут мафией. Однако никакие два мафиози не должны сидеть рядом.

Сколько имеется у ведущего способов раздать карты? Два способа считаются различными, если имеется хотя бы один преподаватель, который является мафией в одном случае, но не является мафией в другом.

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

Количество преподавателей $n(1\le n\le 30)$, которые сидят по кругу.

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

Выведите одно число — количество способов раздать карты.

Примеры