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