Putata and Budada are playing an interesting game. They play this game with a die having $$$n$$$ faces. Every integer between $$$0$$$ and $$$n-1$$$ are written on exactly one face, and when they roll this die, each side will face up with equal probability. In other words, rolling the die will result in a uniform random integer between $$$0$$$ and $$$n-1$$$ with equal probability.

The game has two rounds. In the first round, the following happens:

• Putata will roll the die and get an integer as the result, say $$$x$$$.

In the second round, Budada can choose to do one of the following things:

• End the game, and the score of the game will be $$$x$$$.
• Roll the die again, let the result be $$$y$$$, and the game will end, the score of the game will be $$$x \oplus y$$$. Here $$$\oplus$$$ denotes bitwise exclusive-or operation.

Putata and Budada want to maximize the score of the game, and they are so clever that they will always make the best choice. Please write a program to calculate, for some given $$$n$$$, the expectation of the score of the game.

It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{x}{y}$$$, where $$$x$$$ and $$$y$$$ are integers and $$$y \not \equiv 0 \pmod {998\,244\,353}$$$. Output the integer equal to $$$x\cdot y^{-1}\pmod {998\,244\,353}$$$. In other words, output such an integer $$$a$$$ that $$$0\leq a \lt 998\,244\,353$$$ and $$$a\cdot y\equiv x\pmod {998\,244\,353}$$$.