Dane są dodatnie liczby całkowite $N$ oraz $M$.
Dla każdego $k = 1, 2, \dots, N + M - 1$ niech $\text{ans}_k$ oznacza odpowiedź na następujący problem.
Parę ciągów $(a, b)$, gdzie $a = (a_1, a_2, \dots, a_{N+M-1})$ oraz $b = (b_1, b_2, \dots, b_{N+M-1})$, każdy o długości $N + M - 1$, nazywamy dobrą parą ciągów, jeśli spełnione są wszystkie poniższe warunki:
- $(a_1, b_1) = (1, N + 1)$
- Dla $i = 2, 3, \dots, N + M - 1$ zachodzi jeden z poniższych warunków:
- $(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)$
Dla dobrej pary ciągów $(a, b)$ definiujemy drzewo $T(a, b)$ w następujący sposób:
- Jest to drzewo o $N + M$ wierzchołkach ponumerowanych od $1$ do $N + M$.
- Dla każdego $i = 1, 2, \dots, N + M - 1$ istnieje krawędź łącząca wierzchołek $a_i$ z wierzchołkiem $b_i$.
Dla drzewa niech $\text{dist}(i, j)$ oznacza liczbę krawędzi na ścieżce prostej pomiędzy wierzchołkami $i$ oraz $j$. Wynikiem drzewa nazywamy liczbę par liczb całkowitych $(i, j)$ takich, że $1 \le i < j \le N + M$ oraz $\text{dist}(i, j) = k$.
Oblicz sumę wyników drzew $T(a, b)$ po wszystkich dobrych parach ciągów $(a, b)$, modulo $998244353$.
Oblicz wszystkie wartości $\text{ans}_1, \text{ans}_2, \dots, \text{ans}_{N+M-1}$ i wypisz $\sum_{k=1}^{N+M-1} (\text{ans}_k \oplus k)$, gdzie $\oplus$ oznacza bitową alternatywę rozłączną (XOR).
Wejście
Wejście podane jest w następującym formacie:
N M
- $1 \le N \le 5 \times 10^6$
- $1 \le M \le 5 \times 10^6$
- Wszystkie wartości wejściowe są liczbami całkowitymi.
Wyjście
Wypisz odpowiedź.
Przykład 1
2 2
14
Przykład 2
24 167
21925979855
Przykład 3
4297614 4167924
4162418864110099
Uwaga
W pierwszym przykładzie $(\text{ans}_1, \text{ans}_2, \text{ans}_3) = (6, 4, 2)$. Zatem wartością, którą należy wypisać, jest $(6 \oplus 1) + (4 \oplus 2) + (2 \oplus 3) = 7 + 6 + 1 = 14$.