Сусідні вежі

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

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

Вхідні дані

Єдине число - кількість дисків n (1 ≤ n ≤ 10000), які є у розпорядженні монахів.

Вихідні дані

Єдине число - відповідь до задачі.

Приклади