Задачі
Дороги в королівстві
Дороги в королівстві
В одном королевстве имеется \textbf{N} городов. Чтобы жители могли путешествовать по стране, города должны быть соединены дорогами так, чтобы каждый житель мог проехать из каждого города в каждый.
Однако по главному закону этого королевства каждый год дороги уничтожаются и перестраиваются по-новому. При этом конфигурация дорог каждый год должна быть новая, то есть не должна повторять конфигурацию, уже использованную ранее.
Легенда гласит, что если однажды в королевстве не удастся построить дороги новым способом, то королевство будет завоевано. Ваша задача --- выяснить, сколько лет просуществует королевство.
\InputFile
Одно число - количество городов \textbf{N} (\textbf{1 }≤ \textbf{N} ≤ \textbf{75 })
\OutputFile
В выходном файле должно быть записано, сколько лет просуществует королевство.
Вхідні дані #1
3
Вихідні дані #1
4