掩码汉明重量

题目描述

给定整数 $N$ 和 $M$，计算 $\displaystyle \sum_{k=0}^{N}$ $\rm{popcount}$$(k \mathbin{\&} M)$，并对 $998244353$ 取模。

这里，$\mathbin{\&}$ 表示按位与（bitwise AND）运算。

什么是按位与运算？

非负整数 $a$ 和 $b$ 的按位与运算结果 $x = a \mathbin{\&} b$ 定义如下：

$x$ 是满足以下条件的唯一非负整数：对于所有非负整数 $k$，

• 若 $a$ 的二进制表示中 $2^k$ 位和 $b$ 的二进制表示中 $2^k$ 位都为 $1$，则 $x$ 的二进制表示中 $2^k$ 位为 $1$。
• 否则，$x$ 的二进制表示中 $2^k$ 位为 $0$。

例如，$3=11_{(2)}$，$5=101_{(2)}$，所以 $3 \mathbin{\&} 5 = 1$。

什么是 popcount？

$\rm{popcount}$$(x)$ 表示 $x$ 的二进制表示中 $1$ 的个数。

例如，$13=1101_{(2)}$，所以 $\rm{popcount}$$(13) = 3$。

输入格式

输入按以下格式从标准输入给出：

$N$ $M$

输出格式

输出答案的整数。

样例

4 3

4

$\rm{popcount}$$(0\mathbin{\&}3) = 0$

$\rm{popcount}$$(1\mathbin{\&}3) = 1$

$\rm{popcount}$$(2\mathbin{\&}3) = 1$

$\rm{popcount}$$(3\mathbin{\&}3) = 2$

$\rm{popcount}$$(4\mathbin{\&}3) = 0$

这些值的和为 $4$。

0 0

0

也可能有 $N = 0$ 或 $M = 0$ 的情况。

1152921504606846975 1152921504606846975

499791890

注意结果需要对 $998244353$ 取模。

数据范围

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