Se te da un entero positivo $N$.
Encuentra el número de pares de enteros $(a, b)$ tales que $1 \le a, b < 2^N$ y se satisfaga la siguiente condición, módulo el número primo $998244353$:
- Existe un triángulo no degenerado cuyos lados tienen longitudes $a, b, a \oplus b$.
Aquí, para los enteros $x, y$, $x \oplus y$ denota el OR exclusivo (XOR) a nivel de bits de $x$ e $y$.
Entrada
La primera línea contiene un entero $N$ ($1 \le N \le 10^{18}$).
Salida
Imprime el número de pares de enteros $(a, b)$ que satisfacen la condición, módulo el número primo $998244353$.
Ejemplos
Entrada 1
2
Salida 1
0
Entrada 2
5
Salida 2
390
Entrada 3
10000
Salida 3
851087540
Nota
Para el segundo ejemplo, por ejemplo, $(a, b) = (13, 24)$ satisface la condición. Dado que $a \oplus b = 13 \oplus 24 = 21$, existe un triángulo no degenerado cuyos lados tienen longitudes $13, 24, 21$.
Hay exactamente $390$ pares de enteros $(a, b)$ que satisfacen la condición.
El XOR a nivel de bits $x \oplus y$ de enteros no negativos $x, y$ se define de la siguiente manera:
- En la representación binaria de $x \oplus y$, el dígito en la posición $2^k$ ($k \ge 0$) es $1$ si y solo si exactamente uno de los dígitos en la posición $2^k$ en las representaciones binarias de $x$ e $y$ es $1$; de lo contrario, es $0$.
Por ejemplo, $3 \oplus 5 = 6$ (en binario, $011 \oplus 101 = 110$).