
В зоопарке есть клеток, расположенных в ряд. Среди обитателей — две обезьяны, Хем и Сем. Раньше Хем и Сем были близкими друзьями и всегда сидели в соседних клетках, но теперь они поссорились и не хотят друг друга видеть. Смотритель хочет рассадить их в соответствии с их пожеланиями, но столкнулся с проблемой. Хем и Сем — умные обезьяны (каждая окончила восемь классов!), и им интересно, сколькими способами можно их разместить так, чтобы их клетки не были соседними, причем каждая — в своей клетке. Считайте, что все клеток свободны, а остальные животные готовы переселиться куда угодно.
Смотритель пытался подсчитать варианты, но запутался где-то возле гиппопотамов. Без вашей помощи ему явно не справиться!
В первой строке содержится число клеток (2 \le n \le 100).
Выведите количество способов посадить Хема и Сема в разные, не соседние клетки.
Example 1
Example 2