Giúp nhà vua

Nhà vua cần chọn ra đúng một người trong số $n$ hiệp sĩ, sao cho mỗi hiệp sĩ được chọn với xác suất bằng nhau, tức là đúng $1/n$. Công cụ duy nhất ông có là một đồng xu cân đối: mỗi lần tung, đồng xu ra mặt sấp hoặc mặt ngửa với xác suất $1/2$, độc lập với những lần tung khác.

Nhà vua được phép dùng chiến lược tùy ý: sau mỗi lần tung, dựa trên toàn bộ dãy kết quả đã nhận được, ông quyết định dừng lại và công bố người thắng, hoặc tung thêm một lần nữa. Chiến lược được coi là hợp lệ nếu nó kết thúc với xác suất $1$ và mỗi hiệp sĩ thắng với xác suất đúng bằng $1/n$.

Trong tất cả các chiến lược hợp lệ, nhà vua chọn chiến lược có kỳ vọng số lần tung nhỏ nhất. Hãy tính giá trị kỳ vọng đó.

Dữ liệu vào

Một dòng duy nhất chứa số nguyên $n$.

Dữ liệu ra

In ra kỳ vọng số lần tung nhỏ nhất dưới dạng phân số tối giản a/b (không có dấu cách, không có chữ số 0 vô nghĩa ở đầu). Nếu giá trị là số nguyên $a$ thì in ra dạng a/1; riêng với $n=1$ nhà vua không cần tung lần nào nên đáp án là 0/1.

Ràng buộc

• $1\le n\le 10000$
• Đáp án có thể rất lớn: tử số và mẫu số có thể lên tới khoảng $3000$ chữ số thập phân.

Ví dụ