Бродячий цирк
Бродячий цирк
Один з шаманів (у ті рідкі хвилини, коли він не будує греблі) працює директором бродячого цирка "Ромашка". Стержнем програми цього цирку є виступ індійських та африканських слонів на одній сцені.
У цирку є N слонів, для зручності дресирування вони пронумеровані цілими числами від 1 до N. Цирковий номер зі слонами полягає у тому, що слони у якомусь порядку виходять на сцену і веселять зал з глядачами. Наприклад, якщо у цирку було три слони, то виступ може виглядати як вихід слона під номером один, вихід слона під номером три, вихід слона під номером два.
Для того, щоб глядачі знову і знову повертались у цирк, директор вирішив робити кожну виставу унікальною. Дві вистви вважаються різними, якщо слони в них виступають у різному порядку. Таким чином, кожного нового дня слони виступали у іншому порядку, який до цього жодного разу не зустрічався. У випадку з трьома слонами вони виступали б у наступному порядку:
Директор кожного дня обирає порядок слонів не дуже оригінально: серед можливих виступів він обирає той, у якому слон під номер один виступає раніше усіх. Серед таких він обирає той, у якому слон під номером два виступає раніше усіх і т.д.
ЛКШенята відправились до цирку на N-ий день. Їм дуже сподобалась вистава, і вони вирішили розповісти про неї своїм друзям. На жаль, вони забули, який слон виступав першим. Будь-ласка, допоможіть їм! Напишіть програму, яка допоможе за числом N знайти, який слон виступав першим. Пам'ятайте, що цирк міг існувати вже досить давно.
Вхідні дані
У першому рядку вхідних даних міститься єдине число N (1 ≤ N ≤ 10^5).
Вихідні дані
Виведіть одне число - шуканий номер слона, який виступав першим у N-ий день.
Приклад
3
2