Koza Nostra

Məktəbdə imtahan zamanı müəllimlər mafiya oyunu oynayır. Dairəvi masada $n$ müəllim oturub. Aparıcı, bu müəllimlərdən birinə və ya bir neçəsinə as kartları paylamalıdır (as kartlarının sayı istənilən qədər ola bilər, hətta $0$ da ola bilər) — bu müəllimlər mafiya rolunu oynayacaq. Ancaq heç bir iki mafiya üzvü yan-yana oturmamalıdır.

Aparıcının kartları paylamaq üçün neçə fərqli üsulu var? (İki üsul fərqli sayılır, əgər ən azı bir müəllim bir halda mafiya üzvüdür, digər halda isə deyil).

Giriş verilənləri

Dairədə oturan müəllimlərin sayı $n(1\le n\le 30)$.

Çıxış verilənləri

Kartları paylamağın mümkün üsullarının sayını çıxarın.

Nümunələr