eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

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

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

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

В одном королевстве имеется N городов. Чтобы жители могли путешествовать по стране, города должны быть соединены дорогами так, чтобы каждый житель мог проехать из каждого города в каждый.

Однако по главному закону этого королевства каждый год дороги уничтожаются и перестраиваются по-новому. При этом конфигурация дорог каждый год должна быть новая, то есть не должна повторять конфигурацию, уже использованную ранее.

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

Вхідні дані

Одно число - количество городов N (1 N75 )

Вихідні дані

В выходном файле должно быть записано, сколько лет просуществует королевство.

Приклад

Вхідні дані #1
3
Вихідні дані #1
4