Deskripsi

Anda diberikan sebuah bilangan bulat positif $N$.

Carilah banyaknya pasangan bilangan bulat $(a, b)$ sedemikian sehingga $1 \le a, b < 2^N$ dan memenuhi syarat berikut, modulo bilangan prima $998244353$:

• Terdapat sebuah segitiga tak-degenerat yang panjang sisi-sisinya adalah $a, b, a \oplus b$.

Di sini, untuk bilangan bulat $x, y$, $x \oplus y$ menyatakan XOR bitwise dari $x$ dan $y$.

Masukan

Baris pertama berisi sebuah bilangan bulat $N$. ($1 \le N \le 10^{18}$)

Keluaran

Cetak banyaknya pasangan bilangan bulat $(a, b)$ yang memenuhi syarat, modulo bilangan prima $998244353$.

Contoh

Masukan 1

2

Keluaran 1

0

Masukan 2

5

Keluaran 2

390

Penjelasan

Untuk contoh kedua, misalnya, $(a, b) = (13, 24)$ memenuhi syarat. Karena $a \oplus b = 13 \oplus 24 = 21$, terdapat sebuah segitiga tak-degenerat yang panjang sisi-sisinya adalah $13, 24, 21$.

Terdapat tepat $390$ pasangan bilangan bulat $(a, b)$ yang memenuhi syarat.

Masukan 3

10000

Keluaran 3

851087540

Petunjuk

XOR bitwise $x \oplus y$ dari bilangan bulat tak-negatif $x, y$ didefinisikan sebagai berikut:

• Dalam representasi biner dari $x \oplus y$, digit pada posisi $2^k$ ($k \ge 0$) bernilai $1$ jika dan hanya jika tepat salah satu digit pada posisi $2^k$ dalam representasi biner dari $x$ dan $y$ bernilai $1$; selain itu, nilainya adalah $0$.

Sebagai contoh, $3 \oplus 5 = 6$ (dalam biner, $011 \oplus 101 = 110$).