Có $n$ nam và $n$ nữ tham gia một cuộc thi khiêu vũ. Cuộc thi được tổ chức theo các quy tắc sau:

1. Ban đầu, các nam và nữ được ghép ngẫu nhiên thành $n$ cặp, và tất cả các cặp được sắp xếp theo một vòng tròn.
2. Giám khảo tung đồng xu để xác định số $k$, là 1 hoặc 2 với xác suất bằng nhau. Sau đó, một lần tung đồng xu khác xác định hướng "theo chiều kim đồng hồ" hoặc "ngược chiều kim đồng hồ", cũng với xác suất bằng nhau.
3. Dựa trên kết quả tung đồng xu ở bước trước, các nữ đổi bạn nhảy bằng cách di chuyển trên vòng tròn $k$ vị trí theo hướng tương ứng (trong khi các nam giữ nguyên vị trí).
4. Nếu sau khi di chuyển, một nữ ghép cặp với một nam mà cô ấy đã từng khiêu vũ trong một trong các vòng trước đó, cuộc thi kết thúc và giám khảo xác định người chiến thắng. Nếu không, các cặp hiện tại sẽ khiêu vũ một vòng, giám khảo đánh giá cẩn thận, và sau đó quá trình quay lại bước 2.

Hãy xác định số vòng khiêu vũ kỳ vọng sẽ diễn ra trong cuộc thi.

Dữ liệu vào

Một dòng duy nhất chứa số nguyên $n$ ($2 \le n \le 50$).

Dữ liệu ra

Xuất kết quả với độ chính xác $10^{-9}$.

Ví dụ

Dữ liệu vào 1

3

Dữ liệu ra 1

2.50000000000000000000

Dữ liệu vào 2

5

Dữ liệu ra 2

3.21875000000000000000