Vous recevez un entier positif $N$.

Trouvez le nombre de paires d'entiers $(a, b)$ telles que $1 \le a, b < 2^N$ et que la condition suivante soit satisfaite, modulo le nombre premier 998244353 :

• Il existe un triangle non dégénéré dont les longueurs des côtés sont $a, b, a \oplus b$.

Ici, pour des entiers $x, y$, $x \oplus y$ désigne le XOR bit à bit de $x$ et $y$.

Entrée

La première ligne contient un entier $N$ ($1 \le N \le 10^{18}$).

Sortie

Affichez le nombre de paires d'entiers $(a, b)$ satisfaisant la condition, modulo le nombre premier 998244353.

Exemples

Entrée 1

2

Sortie 1

0

Entrée 2

5

Sortie 2

390

Remarque

Pour le deuxième exemple, par exemple, $(a, b) = (13, 24)$ satisfait la condition. Puisque $a \oplus b = 13 \oplus 24 = 21$, il existe un triangle non dégénéré dont les longueurs des côtés sont 13, 24, 21.

Il existe exactement 390 paires d'entiers $(a, b)$ satisfaisant la condition.

Entrée 3

10000

Sortie 3

851087540

Remarque

Le XOR bit à bit $x \oplus y$ d'entiers non négatifs $x, y$ est défini comme suit :

• Dans la représentation binaire de $x \oplus y$, le chiffre à la position $2^k$ ($k \ge 0$) est 1 si et seulement si exactement un des chiffres à la position $2^k$ dans les représentations binaires de $x$ et $y$ est 1 ; sinon, il est 0.

Par exemple, $3 \oplus 5 = 6$ (en binaire, $011 \oplus 101 = 110$).