Bạn được cho hai số nguyên dương $N$ và $M$.
Với mỗi $k = 1, 2, \dots, N + M - 1$, gọi $\text{ans}_k$ là đáp án cho bài toán sau đây.
Một cặp dãy $(a, b)$, trong đó $a = (a_1, a_2, \dots, a_{N+M-1})$ và $b = (b_1, b_2, \dots, b_{N+M-1})$, mỗi dãy có độ dài $N + M - 1$, được gọi là cặp dãy tốt nếu tất cả các điều kiện sau được thỏa mãn:
- $(a_1, b_1) = (1, N + 1)$
- Với $i = 2, 3, \dots, N + M - 1$, một trong hai điều kiện sau xảy ra:
- $(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)$
Đối với một cặp dãy tốt $(a, b)$, định nghĩa cây $T(a, b)$ như sau:
- Đó là một cây gồm $N + M$ đỉnh được đánh số từ $1$ đến $N + M$.
- Với mỗi $i = 1, 2, \dots, N + M - 1$, có một cạnh nối đỉnh $a_i$ và đỉnh $b_i$.
Đối với một cây, gọi $\text{dist}(i, j)$ là số cạnh trên đường đi đơn giữa hai đỉnh $i$ và $j$. Điểm số của cây được định nghĩa là số cặp số nguyên $(i, j)$ sao cho $1 \le i < j \le N + M$ và $\text{dist}(i, j) = k$.
Hãy tính tổng điểm số của $T(a, b)$ trên tất cả các cặp dãy tốt $(a, b)$, theo modulo $998244353$.
Tính tất cả các giá trị $\text{ans}_1, \text{ans}_2, \dots, \text{ans}_{N+M-1}$, và in ra $\sum_{k=1}^{N+M-1} (\text{ans}_k \oplus k)$, trong đó $\oplus$ ký hiệu phép XOR bit.
Dữ liệu vào
Dữ liệu vào được cho theo định dạng sau:
N M
- $1 \le N \le 5 \times 10^6$
- $1 \le M \le 5 \times 10^6$
- Tất cả các giá trị đầu vào đều là số nguyên.
Dữ liệu ra
In ra đáp án.
Ví dụ 1
2 2
14
Ví dụ 2
24 167
21925979855
Ví dụ 3
4297614 4167924
4162418864110099
Ghi chú
Trong ví dụ thứ nhất, $(\text{ans}_1, \text{ans}_2, \text{ans}_3) = (6, 4, 2)$. Do đó, giá trị cần in ra là $(6 \oplus 1) + (4 \oplus 2) + (2 \oplus 3) = 7 + 6 + 1 = 14$.