Bạn được cho một số nguyên dương $N$.

Hãy tìm số lượng các cặp số nguyên $(a, b)$ sao cho $1 \le a, b < 2^N$ và thỏa mãn điều kiện sau, lấy kết quả theo modulo số nguyên tố $998244353$:

• Tồn tại một tam giác không suy biến có độ dài các cạnh là $a, b, a \oplus b$.

Ở đây, với các số nguyên $x, y$, $x \oplus y$ biểu thị phép toán XOR bit của $x$ và $y$.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $N$ ($1 \le N \le 10^{18}$).

Dữ liệu ra

In ra số lượng các cặp số nguyên $(a, b)$ thỏa mãn điều kiện, lấy kết quả theo modulo số nguyên tố $998244353$.

Ví dụ

Dữ liệu vào 1

2

Dữ liệu ra 1

0

Dữ liệu vào 2

5

Dữ liệu ra 2

390

Dữ liệu vào 3

10000

Dữ liệu ra 3

851087540

Ghi chú

Ví dụ, đối với trường hợp thứ hai, cặp $(a, b) = (13, 24)$ thỏa mãn điều kiện. Vì $a \oplus b = 13 \oplus 24 = 21$, nên tồn tại một tam giác không suy biến có độ dài các cạnh là $13, 24, 21$.

Có đúng $390$ cặp số nguyên $(a, b)$ thỏa mãn điều kiện.

Phép toán XOR bit $x \oplus y$ của các số nguyên không âm $x, y$ được định nghĩa như sau:

• Trong biểu diễn nhị phân của $x \oplus y$, chữ số ở vị trí $2^k$ ($k \ge 0$) bằng $1$ khi và chỉ khi đúng một trong các chữ số ở vị trí $2^k$ trong biểu diễn nhị phân của $x$ và $y$ bằng $1$; ngược lại, nó bằng $0$.

Ví dụ, $3 \oplus 5 = 6$ (trong hệ nhị phân, $011 \oplus 101 = 110$).