Handshakes

A handshake is a greeting in which two people each hold out one hand and clasp them together.

He threw a party with $N$ guests, himself included. To make it fun he recruited the guests at random so that no two of them already knew each other, but against his expectation the ice never broke. He decided the reason was that nobody knew anybody, so he arranged an event in which all $N(N-1)/2$ pairs of people shake hands once each.

He is a very peculiar person. When two people A and B shake hands, he considers A and B to know each other from that moment on. That much you might follow, but he also considers everyone A knew and everyone B knew to know each other. For example, at a party with four people P, Q, R, S, suppose P and Q have already shaken hands and so have R and S, so those two pairs know each other. If P and R now shake hands, then P and R, P and S, Q and R, Q and S all know each other. This is far from how acquaintance really works, but that is how he thinks anyway.

At each step of the event, one pair that has not shaken hands yet is picked uniformly at random among all such pairs, and that pair shakes hands. Write a program that computes the expected value of the index of the handshake at which, by his reasoning, everyone knows everyone else.

The first line contains a natural number $N$, the number of people. ($1 \le N \le 40$)

Print the expected value of the index of the handshake at which everyone knows everyone else. For exact judging, write the answer as a reduced fraction $a/b$ and print $(a \times b^{-1}) \bmod 1\,000\,000\,007$ instead. Here $b^{-1}$ is the multiplicative inverse of $b$ modulo $1\,000\,000\,007$. In this problem the answer exists for every possible input.