Score : $400$ points

问题陈述

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

这里，$\mathbin{\&}$ 表示按位 $\rm{AND}$ 操作。

什么是按位 $\rm{AND}$ 操作？非负整数 $a$ 和 $b$ 之间的按位 $\rm{AND}$ 操作的结果 $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$。什么是 $\rm{popcount}$？$\rm{popcount}$$(x)$ 表示 $x$ 的二进制表示中 $1$ 的数量。 例如，$13=1101_{(2)}$，所以 $\rm{popcount}$$(13) = 3$。

以上为大语言模型 kimi 翻译，仅供参考。

Problem Statement

Given integers $N$ and $M$, compute the sum $\displaystyle \sum_{k=0}^{N}$ $\rm{popcount}$$(k \mathbin{\&} M)$, modulo $998244353$.

Here, $\mathbin{\&}$ represents the bitwise $\rm{AND}$ operation.

What is the bitwise $\rm{AND}$ operation? The result $x = a \mathbin{\&} b$ of the bitwise $\rm{AND}$ operation between non-negative integers $a$ and $b$ is defined as follows:

• $x$ is the unique non-negative integer that satisfies the following conditions for all non-negative integers $k$:

• If the $2^k$ place in the binary representation of $a$ and the $2^k$ place in the binary representation of $b$ are both $1$, then the $2^k$ place in the binary representation of $x$ is $1$.

• Otherwise, the $2^k$ place in the binary representation of $x$ is $0$.

For example, $3=11_{(2)}$ and $5=101_{(2)}$, so $3 \mathbin{\&} 5 = 1$. What is $\rm{popcount}$? $\rm{popcount}$$(x)$ represents the number of $1$s in the binary representation of $x$.
For example, $13=1101_{(2)}$, so $\rm{popcount}$$(13) = 3$.

Constraints

• $N$ is an integer between $0$ and $2^{60} - 1$, inclusive.
• $M$ is an integer between $0$ and $2^{60} - 1$, inclusive.

Input

The input is given from Standard Input in the following format:

$N$ $M$

Output

Print the answer as an integer.

Sample Input 1

4 3

Sample Output 1

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$

The sum of these values is $4$.

Sample Input 2

0 0

Sample Output 2

0

It is possible that $N = 0$ or $M = 0$.

Sample Input 3

1152921504606846975 1152921504606846975

Sample Output 3

499791890

Remember to compute the result modulo $998244353$.