Gegeben sind positive ganze Zahlen $N$ und $M$.
Für jedes $k = 1, 2, \dots, N + M - 1$ bezeichne $\text{ans}_k$ die Antwort auf das folgende Problem.
Ein Paar von Folgen $(a, b)$, wobei $a = (a_1, a_2, \dots, a_{N+M-1})$ und $b = (b_1, b_2, \dots, b_{N+M-1})$ jeweils die Länge $N + M - 1$ haben, heißt ein gutes Folgenpaar, wenn alle folgenden Bedingungen erfüllt sind:
- $(a_1, b_1) = (1, N + 1)$
- Für $i = 2, 3, \dots, N + M - 1$ gilt eine der folgenden Aussagen:
- $(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)$
Für ein gutes Folgenpaar $(a, b)$ definieren wir einen Baum $T(a, b)$ wie folgt:
- Es ist ein Baum mit $N + M$ Knoten, die von $1$ bis $N + M$ nummeriert sind.
- Für jedes $i = 1, 2, \dots, N + M - 1$ gibt es eine Kante, die Knoten $a_i$ und Knoten $b_i$ verbindet.
Für einen Baum sei $\text{dist}(i, j)$ die Anzahl der Kanten auf dem einfachen Pfad zwischen den Knoten $i$ und $j$. Die Punktzahl des Baums ist definiert als die Anzahl der Paare ganzer Zahlen $(i, j)$, für die $1 \le i < j \le N + M$ und $\text{dist}(i, j) = k$ gilt.
Berechne die Summe der Punktzahlen von $T(a, b)$ über alle guten Folgenpaare $(a, b)$ modulo $998244353$.
Berechne alle Werte $\text{ans}_1, \text{ans}_2, \dots, \text{ans}_{N+M-1}$ und gib $\sum_{k=1}^{N+M-1} (\text{ans}_k \oplus k)$ aus, wobei $\oplus$ das bitweise exklusive ODER (XOR) bezeichnet.
Eingabe
Die Eingabe erfolgt im folgenden Format:
N M
- $1 \le N \le 5 \times 10^6$
- $1 \le M \le 5 \times 10^6$
- Alle Eingabewerte sind ganze Zahlen.
Ausgabe
Gib die Antwort aus.
Beispiel 1
2 2
14
Beispiel 2
24 167
21925979855
Beispiel 3
4297614 4167924
4162418864110099
Hinweis
Im ersten Beispiel ist $(\text{ans}_1, \text{ans}_2, \text{ans}_3) = (6, 4, 2)$. Daher lautet der auszugebende Wert $(6 \oplus 1) + (4 \oplus 2) + (2 \oplus 3) = 7 + 6 + 1 = 14$.