该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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

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

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

输入格式

输入整数：

$N$ $M$

输出格式

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

输入输出样例 #1

输入 #1

4 3

输出 #1

4

输入输出样例 #2

输入 #2

0 0

输出 #2

0

输入输出样例 #3

输入 #3

1152921504606846975 1152921504606846975

输出 #3

499791890

说明/提示

样例 1 解释

• $\texttt{popcount(0 \& 3)} = 0$
• $\texttt{popcount(1 \& 3)} = 1$
• $\texttt{popcount(2 \& 3)} = 1$
• $\texttt{popcount(3 \& 3)} = 2$
• $\texttt{popcount(4 \& 3)} = 0$

这些值的和是 $4$。

数据范围

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