Коза Ностра

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

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

Вхідні дані

Кількість викладачів $n(1\le n\le 30)$, які сидять у колі.

Вихідні дані

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

Приклади