큰 변화

트리데뱌토프 왕국에는 $N$개의 도시가 있다. 왕은 $N-1$개의 양방향 항공 노선으로 도시들을 연결하려고 한다. 조건은 다음과 같다.

• 각 항공 노선은 서로 다른 두 도시를 연결한다.
• 어떤 도시에서든 다른 모든 도시로 직항이나 환승을 통해 갈 수 있다.

도시의 접근성을 그 도시와 항공 노선으로 직접 연결된 도시의 수라고 하자. 왕은 왕국의 모든 도시 중 접근성의 최댓값이 가능한 한 크도록 요구한다.

도시들을 요구된 방식으로 연결하는 서로 다른 방법은 모두 몇 가지인가?

입력은 하나의 정수 $N$을 포함한다. $N$은 도시의 수이다. ($2 \le N \le 10^9$)

하나의 정수를 출력한다. 이는 문제의 답이다.

문제의 예시를 설명한다. 세 도시에서 접근성의 최댓값은 2이다. 이 값을 달성하는 서로 다른 연결 방법은 세 가지가 있다: (1,2)(2,3), (1,3)(2,3), (1,2)(1,3).