Grid Path Tree
给定正整数 N,M。称长度均为 N+M−1 的两个整数序列 a,b 为一组合法序列,当且仅当:
- (a1,b1)=(1,N+1);
- 对每个 2≤i≤N+M−1,(ai,bi) 等于 (ai−1+1,bi−1) 或 (ai−1,bi−1+1);
- (aN+M−1,bN+M−1)=(N,N+M)。
对每组合法序列,构造一棵顶点编号为 1 到 N+M 的树:对每个 i,在 ai 与 bi 之间连边。这些边一定构成一棵树。
对于 k=1,2,…,N+M−1,令一棵树的得分为满足 1≤u<v≤N+M 且两点距离恰为 k 的点对数量。距离是两点间简单路径上的边数。
令 ansk 为所有合法序列对应树的得分之和对 998244353 取模后的值。输出
$$\sum_{k=1}^{N+M-1}(\mathrm{ans}_k\mathbin{\oplus}k).$$
⊕ 表示按位异或。注意:先分别求出取模后的 ansk,再与 k 异或,最后进行普通整数求和,最后的和不取模。
输入格式
N M
输出格式
输出一个整数,表示上述求和结果。
数据范围
1≤N,M≤5×106。输入均为整数。
样例 1
输入:
2 2
输出:
14
样例 2
输入:
24 167
输出:
21925979855
样例 3
输入:
4297614 4167924
输出:
4162418864110099