시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 (추가 시간 없음) 64 MB111100.000%

문제

There are $n$ males and $n$ females who participate in a dance competition. The competition is held according to the following rules:

  1. Initially males and females are randomly matched into $n$ couples, and all the couples are arranged in a circle.
  2. The judge flips a coin and determines the number $k$, which is either $1$ or $2$ with equal probability. After that, another flip of a coin determines either "clockwise" or "counter-clockwise" direction, also with equal probability.
  3. In accordance with coin flips on the previous step, females switch partners by moving on the circle by $k$ positions in the corresponding direction (while males remain in place).
  4. If, after moving, a female matches a male with whom she already danced in one of the previous rounds, the competition ends, and judges determine the winners. Otherwise, the current couples dance a round, judges carefully evaluate them, and then the process goes to step $2$.

Determine the expected number of rounds which will be danced during the competition.

입력

A single line containing integer $n$ ($2 \le n \le 50$).

출력

Output the answer with accuracy $10^{-9}$.

예제 입력 1

3

예제 출력 1

2.50000000000000000000

예제 입력 2

5

예제 출력 2

3.21875000000000000000