W zawodach tanecznych bierze udział $n$ mężczyzn i $n$ kobiet. Zawody odbywają się zgodnie z następującymi zasadami:

1. Początkowo mężczyźni i kobiety są losowo dobierani w $n$ par, a wszystkie pary są ustawione w okręgu.
2. Sędzia rzuca monetą i ustala liczbę $k$, która z równym prawdopodobieństwem wynosi 1 lub 2. Następnie kolejny rzut monetą określa kierunek: „zgodnie z ruchem wskazówek zegara” lub „przeciwnie do ruchu wskazówek zegara”, również z równym prawdopodobieństwem.
3. Zgodnie z wynikami rzutów monetą z poprzedniego kroku, kobiety zmieniają partnerów, przesuwając się w okręgu o $k$ pozycji w odpowiednim kierunku (podczas gdy mężczyźni pozostają na swoich miejscach).
4. Jeśli po przesunięciu kobieta zostanie sparowana z mężczyzną, z którym tańczyła już w jednej z poprzednich rund, zawody kończą się, a sędziowie wyłaniają zwycięzców. W przeciwnym razie obecne pary tańczą rundę, sędziowie oceniają je, a następnie proces wraca do kroku 2.

Oblicz oczekiwaną liczbę rund, które zostaną przetańczone podczas zawodów.

Wejście

Pojedyncza linia zawierająca liczbę całkowitą $n$ ($2 \le n \le 50$).

Wyjście

Wypisz wynik z dokładnością $10^{-9}$.

Przykład

Wejście 1

3

Wyjście 1

2.50000000000000000000

Wejście 2

5

Wyjście 2

3.21875000000000000000