Sinulle annetaan positiiviset kokonaisluvut $N$ ja $M$.
Jokaiselle $k = 1, 2, \dots, N + M - 1$, olkoon $\text{ans}_k$ vastaus seuraavaan tehtävään.
Jonoparia $(a, b)$, missä $a = (a_1, a_2, \dots, a_{N+M-1})$ ja $b = (b_1, b_2, \dots, b_{N+M-1})$ ovat molemmat pituudeltaan $N + M - 1$, kutsutaan hyväksi jonopariksi, jos kaikki seuraavat ehdot täyttyvät:
- $(a_1, b_1) = (1, N + 1)$
- Kun $i = 2, 3, \dots, N + M - 1$, jompikumpi seuraavista pätee:
- $(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)$
Hyvälle jonoparille $(a, b)$ määritellään puu $T(a, b)$ seuraavasti:
- Se on puu, jossa on $N + M$ solmua, jotka on numeroitu $1$:stä $N + M$:ään.
- Jokaisella $i = 1, 2, \dots, N + M - 1$ puussa on kaari, joka yhdistää solmun $a_i$ ja solmun $b_i$.
Olkoon puussa $\text{dist}(i, j)$ solmujen $i$ ja $j$ välisen yksinkertaisen polun kaarien lukumäärä. Puun pistemäärä määritellään sellaisten kokonaislukuparien $(i, j)$ lukumääräksi, joille $1 \le i < j \le N + M$ ja $\text{dist}(i, j) = k$.
Laske puiden $T(a, b)$ pistemäärien summa yli kaikkien hyvien jonoparien $(a, b)$, modulo $998244353$.
Laske kaikki arvot $\text{ans}_1, \text{ans}_2, \dots, \text{ans}_{N+M-1}$ ja tulosta $\sum_{k=1}^{N+M-1} (\text{ans}_k \oplus k)$, missä $\oplus$ tarkoittaa bittikohtaista poissulkevaa TAI-operaatiota (XOR).
Syöte
Syöte annetaan seuraavassa muodossa:
N M
- $1 \le N \le 5 \times 10^6$
- $1 \le M \le 5 \times 10^6$
- Kaikki syötteen arvot ovat kokonaislukuja.
Tuloste
Tulosta vastaus.
Esimerkki 1
2 2
14
Esimerkki 2
24 167
21925979855
Esimerkki 3
4297614 4167924
4162418864110099
Huomautus
Ensimmäisessä esimerkissä $(\text{ans}_1, \text{ans}_2, \text{ans}_3) = (6, 4, 2)$. Näin ollen tulostettava arvo on $(6 \oplus 1) + (4 \oplus 2) + (2 \oplus 3) = 7 + 6 + 1 = 14$.