Опис

Задано додатне ціле число $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

Пояснення

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

Усього існує $390$ пар цілих чисел $(a, b)$, що задовольняють умову.

Вхідні дані 3

10000

Вихідні дані 3

851087540

Підказка

Побітове виключне АБО $x \oplus y$ невід'ємних цілих чисел $x, y$ визначається так:

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

Наприклад, $3 \oplus 5 = 6$ (у двійковому записі $011 \oplus 101 = 110$).