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