Дороги в королівстві

У королівстві є N міст. Щоб жителі могли подорожувати, міста повинні бути з'єднані дорогами так, щоб можна було дістатися з будь-якого міста в будь-яке інше.

Однак, згідно з головним законом королівства, щороку дороги знищуються і перебудовуються заново. При цьому конфігурація доріг повинна бути новою, тобто не повторювати жодну з раніше використаних.

Легенда свідчить, що якщо одного разу не вдасться побудувати дороги новим способом, королівство буде завойоване. Ваше завдання — визначити, скільки років королівство зможе існувати.

Вхідні дані

Одне число - кількість міст N (1 ≤ N ≤ 75)

Вихідні дані

У вихідному файлі має бути вказано, скільки років проіснує королівство.

Приклади