악수 Batch Compilation commands

악수는 두 사람이 각자 한 손을 마주 내어 잡고 서로 반가움을 표하며 결속을 다지는 매우 뜻깊은 일이다.

그는 자신을 포함하여 $N$명이 참석하는 파티를 주최했다. 그는 파티의 재미를 위해 모든 참가자들이 이미 알고 있던 사람이 한 명도 없도록 참가자들을 무작위로 모집했으나, 그의 예상과는 달리 얼어붙은 분위기는 잘 깨지지 않았다. 그는 어떻게 하면 자신이 원하던 즐거운 파티를 이끌어낼 수 있을지 고심하다가 이것은 서로가 서로를 잘 알지 못하기 때문이라는 결론을 내리고, 먼저 가지의 모든 사람 쌍에 대해 악수를 한 번씩 하는 행사를 하여 서로의 친목을 다지기로 했다.

그는 매우 독특한 사람이라, 어떤 두 사람 A, B가 악수를 하면 그 즉시 A와 B는 서로 아는 사람이 된다고 생각한다. 거기까지는 이해할 수 있을지 모르지만, 그는 A가 알고 있던 사람들과 B가 알고 있던 사람들 역시 서로 아는 사람이 된다고 생각한다. 예를 들어, 4명의 사람 P, Q, R, S가 참여한 파티에서 P와 Q, R과 S끼리 이미 악수를 해서 서로 아는 사람일 때 P와 R이 악수를 한다면, P와 R, P와 S, Q와 R, Q와 S 모두 서로 아는 사람이 된다. 이는 실제와는 매우 동떨어진 생각이지만 어쨌든 그는 그렇게 생각한다.

악수 행사를 진행할 때는 아직까지 악수를 하지 않은 사람 쌍들 중 하나를 동일한 확률로 무작위로 하나 골라 진행한다고 할 때, 그의 생각 상에서 모든 사람이 서로를 알게 되는 악수는 몇 번째가 될 것인지 그 기댓값을 구하는 프로그램을 작성하라.

입력

첫 번째 줄에는 사람의 수를 나타내는 자연수 $N $이 주어진다.

부분문제

부분문제	점수	N
1	5	1 ≤ N ≤ 5
2	95	1 ≤ N ≤ 40

출력

모든 사람이 서로를 알게 되는 악수는 몇 번째가 될 것인지 그 기댓값을 출력한다. 정확한 판별을 위해, 답을 기약분수로 나타내었을 때 가 된다면, 을 대신 출력하도록 한다. $b^{-1}$은 $b$의 모듈러 곱셈에 대한 역원이다. 이 문제에서는 가능한 모든 입력에 대해 답이 존재한다.

입출력 예제

예제 1

입력

1

출력

0

예제 2

입력

2

출력

1

예제 3

입력

3

출력

2