Сипаттамасы

Сізге оң бүтін $N$ саны берілген.

$1 \le a, b < 2^N$ болатын және келесі шартты қанағаттандыратын $(a, b)$ бүтін сандар жұптарының санын $998244353$ жай санының модулі бойынша табыңыз:

• Қабырғаларының ұзындықтары $a, b, a \oplus b$ болатын азғындалмаған үшбұрыш бар болады.

Мұндағы $x, y$ бүтін сандары үшін $x \oplus y$ өрнегі $x$ пен $y$ сандарының разрядтық XOR амалын білдіреді.

Кіріс деректер

Бірінші жолда бір бүтін $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, y$ сандарының разрядтық XOR-ы $x \oplus y$ былайша анықталады:

• $x \oplus y$ санының екілік жазылуында $2^k$ ($k \ge 0$) разрядындағы цифр тек $x$ пен $y$ сандарының екілік жазылуларындағы $2^k$ разрядындағы цифрлардың дәл біреуі ғана $1$ болғанда $1$-ге тең болады; әйтпесе ол $0$-ге тең.

Мысалы, $3 \oplus 5 = 6$ (екілік жүйеде $011 \oplus 101 = 110$).