Ti vengono dati gli interi positivi $N$ e $M$.
Per ogni $k = 1, 2, \dots, N + M - 1$, sia $\text{ans}_k$ la risposta al seguente problema.
Una coppia di sequenze $(a, b)$, dove $a = (a_1, a_2, \dots, a_{N+M-1})$ e $b = (b_1, b_2, \dots, b_{N+M-1})$, ciascuna di lunghezza $N + M - 1$, è chiamata una buona coppia di sequenze se sono soddisfatte tutte le seguenti condizioni:
- $(a_1, b_1) = (1, N + 1)$
- Per $i = 2, 3, \dots, N + M - 1$, vale una delle seguenti relazioni:
- $(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)$
Per una buona coppia di sequenze $(a, b)$, definiamo un albero $T(a, b)$ come segue:
- È un albero con $N + M$ vertici etichettati da $1$ a $N + M$.
- Per ogni $i = 1, 2, \dots, N + M - 1$, c'è un arco che collega il vertice $a_i$ e il vertice $b_i$.
Per un albero, sia $\text{dist}(i, j)$ il numero di archi sul cammino semplice tra i vertici $i$ e $j$. Il punteggio dell'albero è definito come il numero di coppie di interi $(i, j)$ tali che $1 \le i < j \le N + M$ e $\text{dist}(i, j) = k$.
Calcola la somma dei punteggi di $T(a, b)$ su tutte le buone coppie di sequenze $(a, b)$, modulo $998244353$.
Calcola tutti i valori $\text{ans}_1, \text{ans}_2, \dots, \text{ans}_{N+M-1}$ e stampa $\sum_{k=1}^{N+M-1} (\text{ans}_k \oplus k)$, dove $\oplus$ indica l'OR esclusivo bit a bit (XOR).
Input
L'input è fornito nel seguente formato:
N M
- $1 \le N \le 5 \times 10^6$
- $1 \le M \le 5 \times 10^6$
- Tutti i valori in input sono interi.
Output
Stampa la risposta.
Esempio 1
2 2
14
Esempio 2
24 167
21925979855
Esempio 3
4297614 4167924
4162418864110099
Nota
Nel primo esempio, $(\text{ans}_1, \text{ans}_2, \text{ans}_3) = (6, 4, 2)$. Pertanto, il valore da stampare è $(6 \oplus 1) + (4 \oplus 2) + (2 \oplus 3) = 7 + 6 + 1 = 14$.