Dana jest liczba całkowita dodatnia $N$.

Znajdź liczbę par liczb całkowitych $(a, b)$ takich, że $1 \le a, b < 2^N$ oraz spełniony jest poniższy warunek, modulo liczba pierwsza $998244353$:

• Istnieje trójkąt niezdegenerowany o długościach boków $a, b, a \oplus b$.

Tutaj, dla liczb całkowitych $x, y$, symbol $x \oplus y$ oznacza bitową operację XOR liczb $x$ oraz $y$.

Wejście

W pierwszej linii znajduje się liczba całkowita $N$ ($1 \le N \le 10^{18}$).

Wyjście

Wypisz liczbę par liczb całkowitych $(a, b)$ spełniających warunek, modulo liczba pierwsza $998244353$.

Przykład

Wejście 1

2

Wyjście 1

0

Wejście 2

5

Wyjście 2

390

Wejście 3

10000

Wyjście 3

851087540

Uwagi

Dla drugiego przykładu, na przykład, para $(a, b) = (13, 24)$ spełnia warunek. Ponieważ $a \oplus b = 13 \oplus 24 = 21$, istnieje trójkąt niezdegenerowany o długościach boków $13, 24, 21$.

Istnieje dokładnie $390$ par liczb całkowitych $(a, b)$ spełniających ten warunek.

Bitowa operacja XOR $x \oplus y$ dla nieujemnych liczb całkowitych $x, y$ jest zdefiniowana następująco:

• W reprezentacji binarnej $x \oplus y$, cyfra na pozycji $2^k$ ($k \ge 0$) jest równa $1$ wtedy i tylko wtedy, gdy dokładnie jedna z cyfr na pozycji $2^k$ w reprezentacjach binarnych $x$ oraz $y$ jest równa $1$; w przeciwnym razie jest równa $0$.

Na przykład $3 \oplus 5 = 6$ (binarnie $011 \oplus 101 = 110$).