AT_stpc2025_1_d Grid Path Tree

正整数 $ N, M $ が与えられます。 $ k = 1, 2, \dots, N + M - 1 $ に対して、以下の問題の答えを $ \mathrm{ans}_{k} $ とします。 > 長さ $ N + M - 1 $ の数列 $ a = (a_{1}, a_{2}, \dots , a_{N + M - 1}), b = (b_{1}, b_{2}, \dots, b_{N + M - 1}) $ の組 $ (a, b) $ であって、以下の条件をすべて満たすものを**良い数列の組**とします。 > > - $ (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} $ を結ぶ辺が存在する > > 木に対して頂点 $ i $ と頂点 $ j $ を結ぶ単純パスに含まれる辺の個数を $ \mathrm{dist}(i,j) $ とし、木の**スコア**を $ 1\leq i < j\leq N + M $ かつ $ \mathrm{dist}(i, j) = k $ を満たす整数の組 $ (i, j) $ の個数とします。 > > すべての**良い数列の組** $ (a, b) $ に対する $ T(a, b) $ の**スコア**の総和を $ 998244353 $ で割ったあまりを求めてください。 $ \mathrm{ans}_1, \mathrm{ans}_2, \dots, \mathrm{ans}_{N+M-1} $ をすべて求め、 $ \displaystyle \sum_{k = 1}^{N + M - 1} (\mathrm{ans}_{k}\oplus k) $ を出力してください。ここで、 $ \oplus $ はビットごとの排他的論理和です。 ビットごとの排他的論理和とは 非負整数 $ A,B $ のビットごとの排他的論理和 (XOR) $ A \oplus B $ は、以下のように定義されます。 - $ A \oplus B $ を二進表記した際の $ 2^k \, (k \geq 0) $ の位の数は、 $ A,B $ を二進表記した際の $ 2^k $ の位の数のうち一方のみが $ 1 $ であれば $ 1 $ 、そうでなければ $ 0 $ である。 例えば、 $ 3 \oplus 5 = 6 $ となります (二進表記すると: $ 011 \oplus 101=110 $ )。

入力は以下の形式で与えられる。 > $ N $ $ M $

答えを出力せよ。

### Sample Explanation 1 $ (\mathrm{ans}_1,\mathrm{ans}_2,\mathrm{ans}_3) = (6, 4, 2) $ となるため、出力すべき値は、 $ (6\oplus 1) + (4\oplus 2) + (2\oplus 3) = 7 + 6 + 1 = 14 $ です。 ### Constraints - 入力はすべて整数 - $ 1\leq N\leq 5\times 10^{6} $ - $ 1\leq M\leq 5\times 10^{6} $