On vous donne deux entiers strictement positifs $N$ et $M$.
Pour chaque $k = 1, 2, \dots, N + M - 1$, soit $\text{ans}_k$ la réponse au problème suivant.
Un couple de suites $(a, b)$, où $a = (a_1, a_2, \dots, a_{N+M-1})$ et $b = (b_1, b_2, \dots, b_{N+M-1})$, chacune de longueur $N + M - 1$, est appelé un bon couple de suites si toutes les conditions suivantes sont satisfaites :
- $(a_1, b_1) = (1, N + 1)$
- Pour $i = 2, 3, \dots, N + M - 1$, l'une des propriétés suivantes est vérifiée :
- $(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)$
Pour un bon couple de suites $(a, b)$, on définit un arbre $T(a, b)$ comme suit :
- C'est un arbre à $N + M$ sommets numérotés de $1$ à $N + M$.
- Pour chaque $i = 1, 2, \dots, N + M - 1$, il existe une arête reliant le sommet $a_i$ et le sommet $b_i$.
Pour un arbre, soit $\text{dist}(i, j)$ le nombre d'arêtes sur le chemin simple entre les sommets $i$ et $j$. Le score de l'arbre est défini comme le nombre de couples d'entiers $(i, j)$ tels que $1 \le i < j \le N + M$ et $\text{dist}(i, j) = k$.
Calculez la somme des scores de $T(a, b)$ sur tous les bons couples de suites $(a, b)$, modulo $998244353$.
Calculez toutes les valeurs $\text{ans}_1, \text{ans}_2, \dots, \text{ans}_{N+M-1}$, et affichez $\sum_{k=1}^{N+M-1} (\text{ans}_k \oplus k)$, où $\oplus$ désigne le OU exclusif bit à bit (XOR).
Entrée
L'entrée est donnée dans le format suivant :
N M
- $1 \le N \le 5 \times 10^6$
- $1 \le M \le 5 \times 10^6$
- Toutes les valeurs d'entrée sont des entiers.
Sortie
Affichez la réponse.
Exemple 1
2 2
14
Exemple 2
24 167
21925979855
Exemple 3
4297614 4167924
4162418864110099
Note
Dans le premier exemple, $(\text{ans}_1, \text{ans}_2, \text{ans}_3) = (6, 4, 2)$. Par conséquent, la valeur à afficher est $(6 \oplus 1) + (4 \oplus 2) + (2 \oplus 3) = 7 + 6 + 1 = 14$.