잭과 질

남자 $n$명과 여자 $n$명이 댄스 대회에 참가한다. 대회는 다음 규칙에 따라 진행된다.

1. 처음에 남자와 여자를 무작위로 짝지어 $n$쌍의 커플을 만들고, 모든 커플을 원형으로 배열한다.
2. 심판이 동전을 던져 $k$를 정한다. $k$는 $1$ 또는 $2$이며, 두 값이 나올 확률은 같다. 이어서 다른 동전을 던져 "시계 방향" 또는 "반시계 방향"을 정한다. 이 역시 확률이 같다.
3. 앞 단계의 동전 결과에 따라 여자들은 원 위에서 해당 방향으로 $k$칸씩 이동하며, 도착한 자리의 남자를 새 파트너로 삼는다. 남자는 제자리에 있는다.
4. 이동 후 여자가 이전 라운드에서 함께 춤춘 남자와 다시 짝이 되면 대회가 끝나고, 심판이 우승자를 결정한다. 그렇지 않으면 현재 커플이 한 라운드를 춤추고, 심판이 평가한 뒤 2단계로 돌아간다.

대회 중 춤추는 라운드 수의 기댓값을 구하라.

정수 $n$ ($2 \le n \le 50$)이 한 줄에 주어진다.

답을 $10^{-9}$의 정확도로 출력한다.