파이 쟁탈전

2023년 세종대학교에서는 "파이 쟁탈전"이 열렸다.

"이과는 ChatGPT 하위호환"이라는 문과의 도발을 본 이과는 너무나도 화가 나서 문과를 혼내주기 위해 게임을 준비했다.

바로 "배스킨라빈스 $N$ 게임"이다. 게임의 규칙은 다음과 같다.

• 두 명의 플레이어인 이과와 문과가 턴을 번갈아 가면서 게임을 진행하며, 이과가 먼저 시작한다.
• 각 턴에는 현재까지 불리지 않은 가장 작은 양의 정수부터 차례대로, $1$개 이상 $3$개 이하의 연속된 정수를 부른다.
• $N$을 부르는 플레이어가 패배한다.

이 게임은 너무나도 유명해서 이과는 이 게임의 최선의 전략을 알고 있지만, 문과는 그러한 전략을 모른다.

따라서 이과는 자신의 턴마다, 문과가 어떤 선택을 하더라도 승리할 수 있는 전략이 존재한다면 그 전략에 따라 정수를 부르고, 그렇지 않다면 $1$개를 부른다.

반면에 문과는 자신의 턴마다 $1$개, $2$개, $3$개 중 하나를 동일한 확률로 선택하여 부른다.

정수 $N$이 주어졌을 때, 이과가 승리할 확률을 구하여라.

첫 번째 줄에 정수 $N$이 주어진다. $(1\leq N\leq 10^9)$

첫 번째 줄에 이과가 승리할 확률을 $998\,244\,353$으로 나눈 나머지를 출력한다. $998\,244\,353$은 소수이다.

구체적으로, 가능한 모든 입력에 대해 이과가 승리할 확률이 항상 유리수임을 보일 수 있으며, 이를 기약분수 $p/q$ $(p\ge 0; q>0)$로 나타냈을 때 $qx-p$가 $998\,244\,353$의 배수인 $0$ 이상 $998\,244\,353$ 미만의 정수 $x$가 항상 유일하게 존재한다. 이때, $x$를 출력해야 한다.