Beskrivelse

Du får gitt et positivt heltall $N$.

Finn antallet par av heltall $(a, b)$ slik at $1 \le a, b < 2^N$ og følgende betingelse er oppfylt, modulo primtallet $998244353$:

• Det finnes en ikke-degenerert trekant hvis sidelengder er $a, b, a \oplus b$.

Her betegner $x \oplus y$ for heltall $x, y$ bitvis XOR av $x$ og $y$.

Inndata

Den første linjen inneholder et heltall $N$. ($1 \le N \le 10^{18}$)

Utdata

Skriv ut antallet par av heltall $(a, b)$ som oppfyller betingelsen, modulo primtallet $998244353$.

Eksempler

Inndata 1

2

Utdata 1

0

Inndata 2

5

Utdata 2

390

Forklaring

For det andre eksempelet oppfyller for eksempel $(a, b) = (13, 24)$ betingelsen. Siden $a \oplus b = 13 \oplus 24 = 21$, finnes det en ikke-degenerert trekant hvis sidelengder er $13, 24, 21$.

Det er totalt $390$ par av heltall $(a, b)$ som oppfyller betingelsen.

Inndata 3

10000

Utdata 3

851087540

Hint

Bitvis XOR $x \oplus y$ for ikke-negative heltall $x, y$ er definert som følger:

• I den binære representasjonen av $x \oplus y$ er sifferet på $2^k$-plassen ($k \ge 0$) lik $1$ hvis og bare hvis nøyaktig ett av sifrene på $2^k$-plassen i de binære representasjonene av $x$ og $y$ er $1$; ellers er det $0$.

For eksempel er $3 \oplus 5 = 6$ (i binær form $011 \oplus 101 = 110$).