Дано положительное целое число $N$.

Найдите количество пар целых чисел $(a, b)$ таких, что $1 \le a, b < 2^N$, удовлетворяющих следующему условию, по модулю простого числа $998244353$:

• Существует невырожденный треугольник со сторонами $a, b, a \oplus b$.

Здесь для целых чисел $x, y$ через $x \oplus y$ обозначена побитовая операция XOR (исключающее ИЛИ) чисел $x$ и $y$.

Входные данные

Первая строка содержит целое число $N$ ($1 \le N \le 10^{18}$).

Выходные данные

Выведите количество пар целых чисел $(a, b)$, удовлетворяющих условию, по модулю простого числа $998244353$.

Примеры

Входные данные 1

2

Выходные данные 1

0

Входные данные 2

5

Выходные данные 2

390

Входные данные 3

10000

Выходные данные 3

851087540

Примечание

Для второго примера, например, пара $(a, b) = (13, 24)$ удовлетворяет условию. Так как $a \oplus b = 13 \oplus 24 = 21$, существует невырожденный треугольник со сторонами $13, 24, 21$.

Существует ровно $390$ пар целых чисел $(a, b)$, удовлетворяющих условию.

Побитовая операция XOR $x \oplus y$ для неотрицательных целых чисел $x, y$ определяется следующим образом:

• В двоичной записи $x \oplus y$ цифра в разряде $2^k$ ($k \ge 0$) равна $1$ тогда и только тогда, когда ровно одна из цифр в разряде $2^k$ в двоичных записях $x$ и $y$ равна $1$; в противном случае она равна $0$.

Например, $3 \oplus 5 = 6$ (в двоичной системе $011 \oplus 101 = 110$).