题目描述

给定整数 $N$ 和 $M$，计算以下和的结果，对 998244353 取模:

$\displaystyle \sum_{k=0}^{N} \rm{popcount}(k \mathbin{\&} M)$

这里，$\mathbin{\&}$ 表示按位与运算，$\rm{popcount}(x)$ 表示 $x$ 的二进制表示中 1 的个数。

输入格式

输入整数 $N$ 和 $M$。

输出格式

输出一个整数，表示计算结果。

样例

4 3

4

0 0

0

1152921504606846975 1152921504606846975

499791890

样例解释

【样例1说明】

• $\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。

【样例2说明】
N = 0 或 M = 0 是可能的。

数据范围

$0 \le N,M < 2^{60}$

来源

• AtCoder ABC356D