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

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

输入

4 3

输出

4

样例 2

输入

0 0

输出

0

样例 3

输入

1152921504606846975 1152921504606846975

输出

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$ 取模。