תיאור

נתון מספר שלם חיובי $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

רמז

פעולת ה-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$).