配点 : 100 点
問題文
正整数 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 。
制約
- 所有输入均为整数
- 1\leq N\leq 5\times 10^{6}
- 1\leq M\leq 5\times 10^{6}
入力
输入按以下格式给出。
N M
出力
打印答案。 来自
入力例 1
2 2
出力例 1
14
(\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 。
入力例 2
24 167
出力例 2
21925979855
入力例 3
4297614 4167924
出力例 3
4162418864110099