Дано три кілочка. На першому кілочку знаходяться n дисків зверху донизу за зростанням розмірів диску. Два інші порожні. Потрібно перенести усі диски з першого кілочка на другий. Переносити диски дозволяється лише по одному. Не дозволяється класть більший диск на менший.

Скільки існує допустимих конфігурацій розташування n дисків на трьох кілочках?

Вхідні дані

Одне число n (1 ≤ n ≤ 20).

Вихідні дані

Виведіть кількість допустимих конфігурацій.