Сізге оң бүтін сандар $N$ және $M$ берілген.
Әрбір $k = 1, 2, \dots, N + M - 1$ үшін $\text{ans}_k$ арқылы келесі есептің жауабын белгілейік.
Әрқайсысының ұзындығы $N + M - 1$ болатын $(a, b)$ тізбектер жұбы ($a = (a_1, a_2, \dots, a_{N+M-1})$ және $b = (b_1, b_2, \dots, b_{N+M-1})$) келесі шарттардың барлығы орындалса, жақсы тізбектер жұбы деп аталады:
- $(a_1, b_1) = (1, N + 1)$
- $i = 2, 3, \dots, N + M - 1$ үшін келесілердің бірі орындалады:
- $(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)$
Жақсы тізбектер жұбы $(a, b)$ үшін $T(a, b)$ ағашын келесідей анықтайық:
- Бұл $1$-ден $N + M$-ге дейін нөмірленген $N + M$ төбесі бар ағаш.
- Әрбір $i = 1, 2, \dots, N + M - 1$ үшін $a_i$ төбесі мен $b_i$ төбесін қосатын қыр бар.
Ағаш үшін $\text{dist}(i, j)$ арқылы $i$ және $j$ төбелерінің арасындағы қарапайым жолдағы қырлар санын белгілейік. Ағаштың ұпайы $1 \le i < j \le N + M$ және $\text{dist}(i, j) = k$ болатын $(i, j)$ бүтін сандар жұптарының саны ретінде анықталады.
Барлық жақсы тізбектер жұптары $(a, b)$ бойынша $T(a, b)$ ағаштарының ұпайларының қосындысын $998244353$ модулі бойынша есептеңіз.
Барлық $\text{ans}_1, \text{ans}_2, \dots, \text{ans}_{N+M-1}$ мәндерін есептеп, $\sum_{k=1}^{N+M-1} (\text{ans}_k \oplus k)$ мәнін шығарыңыз, мұндағы $\oplus$ биттік XOR амалын білдіреді.
Кіріс деректер
Кіріс деректер келесі форматта беріледі:
N M
- $1 \le N \le 5 \times 10^6$
- $1 \le M \le 5 \times 10^6$
- Барлық кіріс мәндері бүтін сандар болып табылады.
Шығыс деректер
Жауапты шығарыңыз.
Мысал 1
2 2
14
Мысал 2
24 167
21925979855
Мысал 3
4297614 4167924
4162418864110099
Ескертпе
Бірінші мысалда $(\text{ans}_1, \text{ans}_2, \text{ans}_3) = (6, 4, 2)$. Сондықтан шығарылатын мән $(6 \oplus 1) + (4 \oplus 2) + (2 \oplus 3) = 7 + 6 + 1 = 14$ болады.