الوصف

يُعطى لك عدد صحيح موجب $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$).