Великі зміни#9507
У Тридев'ятому царстві є міст. Король бажає з'єднати ці міста за допомогою n - 1 двосторонньої авіалінії таким чином, щоб:
Кожна авіалінія з'єднувала два різних міста.
З будь-якого міста можна було дістатися до будь-якого іншого, можливо, з пересадками.
Назвемо доступністю міста кількість міст, з якими воно безпосередньо з'єднане авіалініями. Король також хоче, щоб максимальне значення доступності серед усіх міст королівства було якомога більшим.
Скільки існує різних способів з'єднати міста відповідним чином?
Одне ціле число (2 \le n \le 10^9) - кількість міст.
Виведіть одне ціле число - відповідь на задачу.
Приклад 1
Максимальне можливе значення доступності для трьох міст дорівнює . Існують три різні варіанти з'єднання, при яких це значення досягається: і , і , і .