Statement
서브컬쳐 팬덤에서 매년마다 최고의 캐릭터를 뽑는 토너먼트가 여럿 진행되는것을 알고 있나요? 전국 내아내임 토너먼트 역시 그중 하나로, 다음과 같은 방식으로 토너먼트가 진행됩니다.
- 총 명의 캐릭터가 토너먼트에 참여하며 번 작품에서는 총 명의 캐릭터가 참여합니다. 모든 캐릭터는 캐릭터 고유의 호감도를 가지고 있으며, 호감도는 이상 이하의 정수로 표현됩니다. 또한, 모든 캐릭터의 호감도가 다르다고 가정합니다.
Input
첫번째 줄에 가 주어집니다. ()
Output
팀킬 수의 기댓값은 항상 유리수로 표현할 수 있으며, 기약분수 꼴로 표현하였을 때, 가 의 배수가 아닌것을 증명할 수 있습니다. 이때, 를 만족하는 정수 가 유일하게 존재합니다. 이 을 출력해주세요.
Samples
예제 1
입력
1 1
2
출력
1
예제 2
입력
1 2
1 1
출력
0
예제 3
입력
2 2
1 3
출력
499122178