AT_abc356_d [ABC356D] Masked Popcount

题目描述

给你 $2$ 个整数 $N$ 和 $M$，请你求出 $\sum\limits_{k=0}^N \operatorname{popcount}(k \operatorname{and}M)$ 对 $998244353$ 取模后的值。

其中，$\operatorname{and}$ 表示按位与运算，$\operatorname{popcount}(x)$ 表示 $x$ 的二进制表示中 $1$ 的个数（比如 $13=1101_{(2)}$，所以 $\operatorname{popcount}(13)=3$）。

输入格式

输入一行两个整数 $N$ 和 $M$。

输出格式

输出答案，结果对 $998244353$ 取模。

输入输出样例 #1

输入 #1

4 3

输出 #1

4

输入输出样例 #2

输入 #2

0 0

输出 #2

0

输入输出样例 #3

输入 #3

1152921504606846975 1152921504606846975

输出 #3

499791890

说明/提示

数据范围

$0\le N,M\le 2^{60}-1$。

样例解释 1

• $\operatorname{popcount} (0\operatorname{and}3)=0$
• $\operatorname{popcount} (1\operatorname{and}3)=1$
• $\operatorname{popcount} (2\operatorname{and}3)=1$
• $\operatorname{popcount} (3\operatorname{and}3)=2$
• $\operatorname{popcount} (4\operatorname{and}3)=0$

这些值的总和为 $4$。

样例解释 2

可能出现 $N=0$ 或 $M=0$ 的情况。

样例解释 3

请注意答案对 $998244353$ 取模。