악수

악수는 두 사람이 각자 한 손을 내어 마주 잡고 반가움을 표하는 인사다.

그는 자신을 포함해 $N$명이 참석하는 파티를 열었다. 파티를 재미있게 만들려고 이미 아는 사이인 사람이 한 명도 없도록 참가자를 무작위로 모았는데, 예상과 달리 얼어붙은 분위기가 좀처럼 풀리지 않았다. 그는 서로를 잘 모르기 때문이라고 결론짓고, 먼저 $N(N-1)/2$가지 사람 쌍이 모두 한 번씩 악수하는 행사를 열어 친목을 다지기로 했다.

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

행사는 아직 악수하지 않은 사람 쌍 가운데 하나를 매번 같은 확률로 무작위로 골라 진행한다. 그의 생각대로라면 모든 사람이 서로 아는 사이가 되는 악수가 몇 번째인지, 그 기댓값을 구하는 프로그램을 작성하라.

첫째 줄에 사람의 수를 나타내는 자연수 $N$이 주어진다. ($1 \le N \le 40$)

모든 사람이 서로 아는 사이가 되는 악수가 몇 번째인지, 그 기댓값을 출력한다. 정확한 채점을 위해 답을 기약분수 $a/b$로 나타낸 다음 $(a \times b^{-1}) \bmod 1\,000\,000\,007$을 대신 출력한다. 여기서 $b^{-1}$은 $1\,000\,000\,007$을 법으로 하는 $b$의 곱셈 역원이다. 이 문제에서는 가능한 모든 입력에 대해 답이 존재한다.