Kuvaus

Sinulle annetaan positiivinen kokonaisluku $N$.

Etsi sellaisten kokonaislukuparien $(a, b)$ lukumäärä, joilla $1 \le a, b < 2^N$ ja seuraava ehto täyttyy, modulo alkuluku $998244353$:

• On olemassa ei-degeneroitunut kolmio, jonka sivujen pituudet ovat $a, b, a \oplus b$.

Tässä kokonaisluvuille $x, y$ merkintä $x \oplus y$ tarkoittaa lukujen $x$ ja $y$ bittikohtaista XOR-operaatiota.

Syöte

Ensimmäinen rivi sisältää kokonaisluvun $N$. ($1 \le N \le 10^{18}$)

Tuloste

Tulosta ehdon täyttävien kokonaislukuparien $(a, b)$ lukumäärä modulo alkuluku $998244353$.

Esimerkit

Syöte 1

2

Tuloste 1

0

Syöte 2

5

Tuloste 2

390

Selitys

Toisessa esimerkissä esimerkiksi $(a, b) = (13, 24)$ täyttää ehdon. Koska $a \oplus b = 13 \oplus 24 = 21$, on olemassa ei-degeneroitunut kolmio, jonka sivujen pituudet ovat $13, 24, 21$.

Ehdon täyttäviä kokonaislukupareja $(a, b)$ on yhteensä $390$.

Syöte 3

10000

Tuloste 3

851087540

Vihje

Ei-negatiivisten kokonaislukujen $x, y$ bittikohtainen XOR $x \oplus y$ määritellään seuraavasti:

• Luvun $x \oplus y$ binääriesityksessä kohdan $2^k$ ($k \ge 0$) bitti on $1$ jos ja vain jos täsmälleen toinen lukujen $x$ ja $y$ binääriesitysten kohdan $2^k$ biteistä on $1$; muussa tapauksessa se on $0$.

Esimerkiksi $3 \oplus 5 = 6$ (binäärinä $011 \oplus 101 = 110$).