Вам даны положительные целые числа $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$.