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

Сколько существует допустимых конфигураций расположения n дисков на трех колышках?

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

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

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