Великі зміни

Дуже проста

Обмеження на час виконання 1 секунда

Обмеження на використання пам'яті 128 мегабайтів

У Тридев'ятому царстві є n міст. Король бажає з'єднати ці міста за допомогою n - 1 двосторонньої авіалінії таким чином, щоб:

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

Назвемо доступністю міста кількість міст, з якими воно безпосередньо з'єднане авіалініями. Король також хоче, щоб максимальне значення доступності серед усіх міст королівства було якомога більшим.

Скільки існує різних способів з'єднати міста відповідним чином?

Вхідні дані

Одне ціле число n (2 ≤ n ≤ 10^9) - кількість міст.

Вихідні дані

Виведіть одне ціле число - відповідь на задачу.

Приклади

Вхідні дані #1

Відповідь #1

Примітка

Максимальне можливе значення доступності для трьох міст дорівнює 2. Існують три різні варіанти з'єднання, при яких це значення досягається: (1,2) і (2,3), (1,3) і (2,3), (1,2) і (1,3).

Відправки 114

Коефіцієнт прийняття 48%