Вам дано додатні цілі числа $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$.