Задача J. Единичная проблема ≡

Условие

Сколько существует двоичных чисел длины n, таких, что в их записи количество единиц больше количества нулей?

Формат входных данных

В единственной строке записано натуральное число n - длина двоичных чисел.

Формат выходных данных

Выведете одно натуральное число - ответ на задачу. Гарантируется, что он не превысит 10¹⁸

Ограничения

1 ≤ n ≤ 50

Система оценки и описание подзадач

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.

Подзадача 1: 1 ≤ n ≤ 16, баллы: 30.

Подзадача 2: нет дополнительных ограничений, баллы: 70.

Пояснение к примеру:

Существует четыре четырехзначных двоичных числа, в записи которых количество единиц больше количества нулей: 1011, 1101, 1110 и 1111.

Примеры тестов

4

4