Koza Nostra#5103
While the students are taking an exam, the teachers are playing Mafia. There are teachers sitting around a round table. The host must deal ace cards to some of them (the number of aces can be arbitrary, including ) — these teachers will be the mafia. However, no two mafia members are allowed to sit next to each other.
In how many ways can the host deal the cards? Two ways are considered different if there exists at least one teacher who is a mafia member in one case and is not a mafia member in the other.
The number of teachers n~(1 \le n \le 30) sitting around the table.
Print one integer — the number of ways to deal the cards.
Beispiel 1
Beispiel 2