Background

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

Problem Description

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 $x<t$, update the range $[l,r]$ to $[x+1,r]$. If $x>t$, 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.

Input Format

One line with one integer $n$.

Output Format

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

3

665496236

Hint

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.

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