Descrizione
Ti viene dato un intero positivo $N$.
Trova il numero di coppie di interi $(a, b)$ tali che $1 \le a, b < 2^N$ e sia soddisfatta la seguente condizione, modulo il numero primo $998244353$:
- Esiste un triangolo non degenere i cui lati hanno lunghezze $a, b, a \oplus b$.
Qui, per gli interi $x, y$, $x \oplus y$ indica lo XOR bit a bit di $x$ e $y$.
Input
La prima riga contiene un intero $N$. ($1 \le N \le 10^{18}$)
Output
Stampa il numero di coppie di interi $(a, b)$ che soddisfano la condizione, modulo il numero primo $998244353$.
Esempi
Input 1
2
Output 1
0
Input 2
5
Output 2
390
Spiegazione
Per il secondo esempio, ad esempio, $(a, b) = (13, 24)$ soddisfa la condizione. Poiché $a \oplus b = 13 \oplus 24 = 21$, esiste un triangolo non degenere i cui lati hanno lunghezze $13, 24, 21$.
Ci sono $390$ coppie di interi $(a, b)$ che soddisfano la condizione.
Input 3
10000
Output 3
851087540
Suggerimento
Lo XOR bit a bit $x \oplus y$ di due interi non negativi $x, y$ è definito come segue:
- Nella rappresentazione binaria di $x \oplus y$, la cifra nella posizione $2^k$ ($k \ge 0$) è $1$ se e solo se esattamente una delle cifre nella posizione $2^k$ nelle rappresentazioni binarie di $x$ e $y$ è $1$; altrimenti è $0$.
Ad esempio, $3 \oplus 5 = 6$ (in binario, $011 \oplus 101 = 110$).