Beschreibung

Gegeben ist eine positive ganze Zahl $N$.

Bestimmen Sie die Anzahl der Paare ganzer Zahlen $(a, b)$ mit $1 \le a, b < 2^N$, die die folgende Bedingung erfüllen, modulo der Primzahl $998244353$:

• Es existiert ein nicht-entartetes Dreieck mit den Seitenlängen $a, b, a \oplus b$.

Hierbei bezeichnet $x \oplus y$ für ganze Zahlen $x, y$ das bitweise XOR von $x$ und $y$.

Eingabe

Die erste Zeile enthält eine ganze Zahl $N$. ($1 \le N \le 10^{18}$)

Ausgabe

Geben Sie die Anzahl der Paare ganzer Zahlen $(a, b)$, die die Bedingung erfüllen, modulo der Primzahl $998244353$ aus.

Beispiele

Eingabe 1

2

Ausgabe 1

0

Eingabe 2

5

Ausgabe 2

390

Erklärung

Im zweiten Beispiel erfüllt beispielsweise $(a, b) = (13, 24)$ die Bedingung. Da $a \oplus b = 13 \oplus 24 = 21$ gilt, existiert ein nicht-entartetes Dreieck mit den Seitenlängen $13, 24, 21$.

Es gibt insgesamt $390$ Paare ganzer Zahlen $(a, b)$, die die Bedingung erfüllen.

Eingabe 3

10000

Ausgabe 3

851087540

Hinweis

Das bitweise XOR $x \oplus y$ zweier nichtnegativer ganzer Zahlen $x, y$ ist wie folgt definiert:

• In der Binärdarstellung von $x \oplus y$ ist die Ziffer an der Stelle $2^k$ ($k \ge 0$) genau dann $1$, wenn in den Binärdarstellungen von $x$ und $y$ genau eine der Ziffern an der Stelle $2^k$ gleich $1$ ist; andernfalls ist sie $0$.

Beispielsweise gilt $3 \oplus 5 = 6$ (in Binärdarstellung $011 \oplus 101 = 110$).