Задача D. Компьютерный ЕГЭ ≡

Условие

Ура, теперь ЕГЭ по информатике будет проходить с использованием компьютера! Больше остальных рад Богдан - теперь он сможет на каждое задание написать программу, проверяющую точность его расчетов, чтобы обезопасить себя от случайных ошибок. А поскольку Богдан в совершенстве владеет динамическим программированием, он сможет написать не просто переборное решение, а гораздо более эффективное. Вот взять хотя бы подсчет количества решений логического уравнения x₁→ x₂→ x₃→ ... → x_n = 1. Долго ли, зная n, решить это задание? Богдан справился за пять минут. А Вы?

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

Единственная строка входного файла содержит натуральное число n.

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

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

Ограничения

2 ≤ n ≤ 52

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

Баллы за каждый тест начисляются независимо.

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

В примере дано n = 2. Есть три решения уравнения x₁→ x₂ = 1, это (0, 0), (0, 1) и (1, 1).

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

2

3