Поки у школярів йде залік, викладачі грають у мафію. У колі сидить $n$ викладачів. Ведучий повинен роздати комусь з них карти с тузами (тузів довільні кількість, можливо $0$) --- ці викладачі будуть мафією. Проте ніякі два мафіозі не повинні сидіти поряд. Скільки способів роздати карти є у ведучого? (Два способи вважаються різними, якщо є хоча б один викладач, який є мафією у одному випадку, але не є в іншому). \InputFile Кількість викладачів $n\:(1 \le n \le 30)$, які сидять у колі. \OutputFile Виведіть одне число --- кількість способів роздати карти.