正の整数 $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$ を結ぶ辺が存在する。
木に対して、頂点 $i$ と頂点 $j$ の間の単純パス上の辺の本数を $\text{dist}(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
注記
1つ目の例では、$(\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$ となります。