P8307 〈 TREE's OI 2022 Spring 〉Absolutely Simple Game

rin and len are playing an absolutely simple game, and pcq is the referee.

Initially, the range $[l,r]=[1,n]$ is given. pcq uniformly randomly selects a natural number $t$ from it. Then rin and len take turns to operate, with rin moving first. On each turn, the current player guesses an integer $x\in[l,r]$. If $x=t$, the game ends and the current player loses. If $xt$, update the range $[l,r]$ to $[l,x-1]$. Both rin and len fully understand the rules and are extremely cute and smart (they will both maximize their own winning probability). During the game, everyone knows all information on the table except $t$. Find rin's winning probability.

One line with one integer $n$.

One line with one integer, representing rin's winning probability, output the fraction $\bmod~998244353$.

**Sample Explanation 1:** rin's winning probability is $\dfrac 23$ (guess $2$ at the beginning). After taking $\bmod~998244353$, the output is $665496236$. *** **This problem uses bundled SubTask testing.** | SubTask ID | Score | Special Constraints | | :-----------: | :-----------: | :-----------: | | $0$ | $10$ | $n\equiv 0\ \pmod 2$ | | $1$ | $20$ | $n\le 100$ | | $2$ | $30$ | $n\le 10^9$ | | $3$ | $40$ | $n\le 10^{18}$ | For $100\%$ of the testdata, $1 \le n\le 10^{18}$. --- **How to take a rational number modulo?** $\dfrac {x}{y} \bmod m$ is defined as $xy^{m-2}\bmod~m$. $m$ must be a prime. It is guaranteed that, after reducing the fraction, the denominator is not a multiple of $998244353$. Translated by ChatGPT 5