Se te dan dos enteros positivos $N$ y $M$.
Para cada $k = 1, 2, \dots, N + M - 1$, sea $\text{ans}_k$ la respuesta al siguiente problema.
Un par de sucesiones $(a, b)$, donde $a = (a_1, a_2, \dots, a_{N+M-1})$ y $b = (b_1, b_2, \dots, b_{N+M-1})$, cada una de longitud $N + M - 1$, se denomina un buen par de sucesiones si se cumplen todas las condiciones siguientes:
- $(a_1, b_1) = (1, N + 1)$
- Para $i = 2, 3, \dots, N + M - 1$, se cumple una de las siguientes opciones:
- $(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)$
Para un buen par de sucesiones $(a, b)$, define un árbol $T(a, b)$ como sigue:
- Es un árbol con $N + M$ vértices etiquetados de $1$ a $N + M$.
- Para cada $i = 1, 2, \dots, N + M - 1$, hay una arista que conecta el vértice $a_i$ y el vértice $b_i$.
Para un árbol, sea $\text{dist}(i, j)$ el número de aristas en el camino simple entre los vértices $i$ y $j$. La puntuación del árbol se define como el número de pares de enteros $(i, j)$ tales que $1 \le i < j \le N + M$ y $\text{dist}(i, j) = k$.
Calcula la suma de las puntuaciones de $T(a, b)$ sobre todos los buenos pares de sucesiones $(a, b)$, módulo $998244353$.
Calcula todos los valores $\text{ans}_1, \text{ans}_2, \dots, \text{ans}_{N+M-1}$ e imprime $\sum_{k=1}^{N+M-1} (\text{ans}_k \oplus k)$, donde $\oplus$ denota el OR exclusivo bit a bit (XOR).
Entrada
La entrada se proporciona en el siguiente formato:
N M
- $1 \le N \le 5 \times 10^6$
- $1 \le M \le 5 \times 10^6$
- Todos los valores de entrada son enteros.
Salida
Imprime la respuesta.
Ejemplo 1
2 2
14
Ejemplo 2
24 167
21925979855
Ejemplo 3
4297614 4167924
4162418864110099
Nota
En el primer ejemplo, $(\text{ans}_1, \text{ans}_2, \text{ans}_3) = (6, 4, 2)$. Por lo tanto, el valor que se debe imprimir es $(6 \oplus 1) + (4 \oplus 2) + (2 \oplus 3) = 7 + 6 + 1 = 14$.