#P17930. Grid Path Tree

Grid Path Tree

Grid Path Tree

给定正整数 N,MN,M。称长度均为 N+M−1N+M-1 的两个整数序列 a,ba,b 为一组合法序列,当且仅当:

  • (a1,b1)=(1,N+1)(a_1,b_1)=(1,N+1);
  • 对每个 2≤i≤N+M−12\le i\le N+M-1,(ai,bi)(a_i,b_i) 等于 (ai−1+1,bi−1)(a_{i-1}+1,b_{i-1}) 或 (ai−1,bi−1+1)(a_{i-1},b_{i-1}+1);
  • (aN+M−1,bN+M−1)=(N,N+M)(a_{N+M-1},b_{N+M-1})=(N,N+M)。

对每组合法序列,构造一棵顶点编号为 11 到 N+MN+M 的树:对每个 ii,在 aia_i 与 bib_i 之间连边。这些边一定构成一棵树。

对于 k=1,2,…,N+M−1k=1,2,\ldots,N+M-1,令一棵树的得分为满足 1≤u<v≤N+M1\le u<v\le N+M 且两点距离恰为 kk 的点对数量。距离是两点间简单路径上的边数。

令 ansk\mathrm{ans}_k 为所有合法序列对应树的得分之和对 998244353998244353 取模后的值。输出

$$\sum_{k=1}^{N+M-1}(\mathrm{ans}_k\mathbin{\oplus}k).$$

⊕\oplus 表示按位异或。注意:先分别求出取模后的 ansk\mathrm{ans}_k,再与 kk 异或,最后进行普通整数求和,最后的和不取模。

输入格式

N M

输出格式

输出一个整数,表示上述求和结果。

数据范围

1≤N,M≤5×1061\le N,M\le5\times10^6。输入均为整数。

样例 1

输入:

2 2

输出:

14

样例 2

输入:

24 167

输出:

21925979855

样例 3

输入:

4297614 4167924

输出:

4162418864110099