Beskrivning

Du får ett positivt heltal $N$.

Hitta antalet par av heltal $(a, b)$ sådana att $1 \le a, b < 2^N$ och följande villkor är uppfyllt, modulo primtalet $998244353$:

• Det existerar en icke-degenererad triangel vars sidlängder är $a, b, a \oplus b$.

Här betecknar $x \oplus y$ för heltal $x, y$ bitvis XOR av $x$ och $y$.

Indata

Den första raden innehåller ett heltal $N$. ($1 \le N \le 10^{18}$)

Utdata

Skriv ut antalet par av heltal $(a, b)$ som uppfyller villkoret, modulo primtalet $998244353$.

Exempel

Indata 1

2

Utdata 1

0

Indata 2

5

Utdata 2

390

Förklaring

För det andra exemplet uppfyller till exempel $(a, b) = (13, 24)$ villkoret. Eftersom $a \oplus b = 13 \oplus 24 = 21$ existerar det en icke-degenererad triangel vars sidlängder är $13, 24, 21$.

Det finns totalt $390$ par av heltal $(a, b)$ som uppfyller villkoret.

Indata 3

10000

Utdata 3

851087540

Tips

Bitvis XOR $x \oplus y$ för icke-negativa heltal $x, y$ definieras enligt följande:

• I den binära representationen av $x \oplus y$ är siffran på position $2^k$ ($k \ge 0$) lika med $1$ om och endast om exakt en av siffrorna på position $2^k$ i de binära representationerna av $x$ och $y$ är $1$; annars är den $0$.

Till exempel är $3 \oplus 5 = 6$ (binärt $011 \oplus 101 = 110$).