Соседние башни

Решите задачу о ханойских башнях в предположении, что переносить диски можно только между соседними башнями.

Решение по-прежнему должно оставаться оптимальным, т.е. перенести все диски с первого стержня на третий нужно за минимальное количество ходов. Как и прежде запрещено ложить большие диски на меньшие.

Входные данные

Единственное число - количество дисков n (1 ≤ n ≤ 10000), имеющихся в распоряжении монахов.

Выходные данные

Единственное число - ответ к задаче.

Примеры