2023년 세종대학교에서는 "파이 쟁탈전"이 열렸다.
"이과는 ChatGPT 하위호환"이라는 문과의 도발을 본 이과는 너무나도 화가 나서 문과를 혼내주기 위해 게임을 준비했다.
바로 "배스킨라빈스 게임"이다. 게임의 규칙은 다음과 같다.
이 게임은 너무나도 유명해서 이과는 이 게임의 최선의 전략을 알고 있지만, 문과는 그러한 전략을 모른다.
따라서 이과는 자신의 턴마다, 문과가 어떤 선택을 하더라도 승리할 수 있는 전략이 존재한다면 그 전략에 따라 정수를 부르고, 그렇지 않다면 개를 부른다.
반면에 문과는 자신의 턴마다 개, 개, 개 중 하나를 동일한 확률로 선택하여 부른다.
정수 이 주어졌을 때, 이과가 승리할 확률을 구하여라.
첫 번째 줄에 정수 이 주어진다.
첫 번째 줄에 이과가 승리할 확률을 으로 나눈 나머지를 출력한다. 은 소수이다.
구체적으로, 가능한 모든 입력에 대해 이과가 승리할 확률이 항상 유리수임을 보일 수 있으며, 이를 기약분수 로 나타냈을 때 가 의 배수인 이상 미만의 정수 가 항상 유일하게 존재한다. 이때, 를 출력해야 한다.
