給定正整數 $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)$ 如下:
- 它是一棵擁有 $N + M$ 個頂點的樹,頂點編號為 $1$ 到 $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$。