Lýsing

Gefin er jákvæð heiltala $N$.

Finndu fjölda para af heiltölum $(a, b)$ þannig að $1 \le a, b < 2^N$ og eftirfarandi skilyrði sé uppfyllt, modulo frumtalan $998244353$:

• Til er óúrkynjaður þríhyrningur sem hefur hliðarlengdirnar $a, b, a \oplus b$.

Hér táknar $x \oplus y$ fyrir heiltölur $x, y$ bitbundið XOR af $x$ og $y$.

Inntak

Fyrsta línan inniheldur heiltölu $N$. ($1 \le N \le 10^{18}$)

Úttak

Prentaðu fjölda para af heiltölum $(a, b)$ sem uppfylla skilyrðið, modulo frumtalan $998244353$.

Dæmi

Inntak 1

2

Úttak 1

0

Inntak 2

5

Úttak 2

390

Skýring

Í öðru dæminu uppfyllir til dæmis $(a, b) = (13, 24)$ skilyrðið. Þar sem $a \oplus b = 13 \oplus 24 = 21$ er til óúrkynjaður þríhyrningur með hliðarlengdirnar $13, 24, 21$.

Alls eru $390$ pör af heiltölum $(a, b)$ sem uppfylla skilyrðið.

Inntak 3

10000

Úttak 3

851087540

Vísbending

Bitbundið XOR $x \oplus y$ fyrir óneikvæðar heiltölur $x, y$ er skilgreint sem hér segir:

• Í tvíundarframsetningu $x \oplus y$ er tölustafurinn í sæti $2^k$ ($k \ge 0$) jafn $1$ ef og aðeins ef nákvæmlega annar tölustafanna í sæti $2^k$ í tvíundarframsetningum $x$ og $y$ er $1$; annars er hann $0$.

Til dæmis er $3 \oplus 5 = 6$ (í tvíundarkerfi $011 \oplus 101 = 110$).