Help King

이 문제는 공식 라운드에서 사용된 문제를 수정한 것이다. 안타깝게도 원래 문제에 대한 저자의 풀이가 잘못된 것으로 밝혀져, 아카이브를 위해 특별히 문제를 변경했다.

옛날 옛적 머나먼 왕국에 왕이 살고 있었다. The King에게는 Victoria라는 아름다운 딸이 있었다. 그들은 행복하게 살았지만, 영원히 행복하게 살지는 못했다. 어느 날 사악한 용이 왕국을 공격하여 Victoria를 납치했다. The King은 슬픔에 잠겼지만, 고귀한 기사들을 모아 그 지옥의 괴물에게서 소녀를 구하는 자에게 왕국의 절반과 Victoria와 결혼할 권리를 주겠다고 약속했다.

한동안 여행한 끝에 기사들은 용의 소굴을 발견했고, 모두 Victoria를 구하기 위해 그곳으로 달려갔다. 각 기사는 용에게 한 번씩 침을 뱉었고, 용의 심장은 상당히 여리고 약했기 때문에 그 심장이 무너져 불쌍한 괴물은 죽고 말았다. 고귀한 기사들은 Victoria를 왕에게 바로 데려갔고, 저마다 소녀와 결혼할 권리를 원했기 때문에 싸움을 벌이기 시작했다.

문제는 모든 고귀한 기사가 똑같이 고귀하고 똑같이 잘생겼으며, Victoria는 어차피 그들 중 누구와도 결혼하고 싶어 하지 않았다는 것이다. Then the King은 (그리고 그는 매우 현명한 사람이어서 누구의 감정도 상하게 하고 싶지 않았다) 누가 자신의 딸을 얻게 될지를 무작위로, 즉 동전을 던져 정하기로 했다. 하지만 고귀한 기사는 n명이었고 동전에는 면이 두 개뿐이었다. 다행인 점은 동전을 던지면 각 면이 같은 확률로 나온다는 것이다. The King은 이 동전을 사용하여 모든 기사가 선택될 확률이 같도록 고귀한 기사 한 명을 고르는 방법에 관심을 갖게 되었다(이 경우 그 확률은 항상 1 / n이어야 한다). First the King은 승자를 결정하기 위해 동전을 던져야 하는 횟수의 기댓값을 알고 싶어 한다. 또한 동전을 던지는 동안 왕은 최적의 던지기 전략(즉, 던지는 횟수의 기댓값을 최소화하는 전략)을 따라야 한다. 이 어려운 과제에서 Help the King.

첫 번째 줄에는 문제 설명의 정수 n 하나가 주어진다 (1 ≤ n ≤ 10000).

구하는 동전 던지기 횟수의 기댓값을 기약분수로 다음 형식에 맞춰 출력한다: "a/b" (따옴표 제외). 앞에 불필요한 영을 붙이지 않는다.