أُعطيَ لك عددان صحيحان موجبان $N$ و $M$.
لكل $k = 1, 2, \dots, N + M - 1$، ليكن $\text{ans}_k$ هو إجابة المسألة التالية.
يُسمّى زوج المتتاليات $(a, b)$، حيث $a = (a_1, a_2, \dots, a_{N+M-1})$ و $b = (b_1, b_2, \dots, b_{N+M-1})$ وطول كل منهما $N + M - 1$، زوجاً جيداً من المتتاليات إذا تحققت جميع الشروط التالية:
- $(a_1, b_1) = (1, N + 1)$
- من أجل $i = 2, 3, \dots, N + M - 1$، يتحقق أحد الشرطين التاليين:
- $(a_i, b_i) = (a_{i-1} + 1, b_{i-1})$
- $(a_i, b_i) = (a_{i-1}, b_{i-1} + 1)$
- $(a_{N+M-1}, b_{N+M-1}) = (N, N + M)$
من أجل زوج جيد من المتتاليات $(a, b)$، نعرّف شجرة $T(a, b)$ كما يلي:
- هي شجرة تتكون من $N + M$ رؤوس مرقمة من $1$ إلى $N + M$.
- لكل $i = 1, 2, \dots, N + M - 1$، يوجد ضلع يصل بين الرأس $a_i$ والرأس $b_i$.
من أجل شجرة، ليكن $\text{dist}(i, j)$ هو عدد الأضلاع على المسار البسيط بين الرأسين $i$ و $j$. تُعرّف نتيجة الشجرة بأنها عدد أزواج الأعداد الصحيحة $(i, j)$ التي تحقق $1 \le i < j \le N + M$ و $\text{dist}(i, j) = k$.
احسب مجموع نتائج $T(a, b)$ على جميع أزواج المتتاليات الجيدة $(a, b)$، بباقي القسمة على $998244353$.
احسب جميع القيم $\text{ans}_1, \text{ans}_2, \dots, \text{ans}_{N+M-1}$، واطبع $\sum_{k=1}^{N+M-1} (\text{ans}_k \oplus k)$، حيث يرمز $\oplus$ إلى عملية XOR للبتات.
الإدخال
يُعطى الإدخال بالصيغة التالية:
N M
- $1 \le N \le 5 \times 10^6$
- $1 \le M \le 5 \times 10^6$
- جميع قيم الإدخال هي أعداد صحيحة.
الإخراج
اطبع الإجابة.
مثال 1
2 2
14
مثال 2
24 167
21925979855
مثال 3
4297614 4167924
4162418864110099
ملاحظة
في المثال الأول، $(\text{ans}_1, \text{ans}_2, \text{ans}_3) = (6, 4, 2)$. لذلك، القيمة المطلوب طباعتها هي $(6 \oplus 1) + (4 \oplus 2) + (2 \oplus 3) = 7 + 6 + 1 = 14$.