In this editorial, we use the following expressions.

The \(j\)-th bit of \(x\): the \(2^j\)s place of \(x\) in its binary representation.
The \(j\)-th bit of \(x\) is set: the \(2^j\)s place of \(x\) in its binary representation is \(1\).

---

The expression can be deformed as follows.

\(\displaystyle \sum_{k=0}^{N} \rm{popcount}\)\((k \mathbin{\&} M) = \) \(\displaystyle \sum_{k=0}^{N} (\) the number of bits set in \((k \mathbin{\&} M))\)
\(\displaystyle = \sum_{k=0}^{N} \sum_{j=0}^{\infty}\) \((1\) if the \(j\)-th bit of \((k \mathbin{\&} M)\) is set, and \(0\) otherwise\()\)
\(\displaystyle = \sum_{j=0}^{\infty} \sum_{k=0}^{N}\) \((1\) if the \(j\)-th bit of \((k \mathbin{\&} M)\) is set, and \(0\) otherwise\()\).

\((1\) if the \(j\)-th bit of \((k \mathbin{\&} M)\) is set, and \(0\) otherwise\()\) can be rephrased as follows.

• If the \(j\)-th bit of \(M\) is not set, always \(0\).
• If the \(j\)-th bit of \(M\) is set:
  • if the \(j\)-th bit of \(k\) is set, \(1\).
  • if the \(j\)-th bit of \(k\) is not set, \(0\).

Under the constraints of this problem, the \(60\)-th and higher bits of \(M\) is always \(0\), so the sought sum can be found by the following procedure.

• For \(j=0,1,\dots,59\), repeat the following:
  • If the \(j\)-th bit of \(M\) is not set, do nothing.
  • If the \(j\)-th bit of \(M\) is set, add the number of integers between \(0\) and \(N\) (inclusive) whose \(j\)-th bit is set to the answer.

All that left is to count the following:

Among the integers between \(0\) and \(N\) (inclusive), how many has the \(j\)-th bit set?

For instance, consider \(j=2\).
The integers with the \(2\)-nd bit set are \(4,5,6,7,12,13,14,15,20,21,22,23,28\dots\).
If you closely look at this sequence, we notice the following fact:

• For a non-negative integer \(k\), among the integers between \(0\) (inclusive) and \(k \times 2^{j+1}\) (exclusive), there are \(k \times 2^j\) integers whose \(j\)-th bit is set.

This can be proved by the facts that the \(j\)-th bit of \(i\) and \(i+2^{j+1}\) coincide for all non-negative integers \(j\), and that there are exactly \(2^j\) integers between \(0\) (inclusive) and \(2^{j+1}\) (exclusive) whose \(j\)-th bit is set.

Moreover, we have the following fact:

• Let \(k\) be a non-negative integer and \(l\) be an integer strictly less than \(k \times 2^{j+1}\); then among the integers between \(k \times 2^{j+1}\) (inclusive) and \(k \times 2^{j+1} + l\) (exclusive), the number of integers whose \(j\)-th bit is set is:
  • \(0\) if \(l\) is strictly less than \(2^j\);
  • \(l - 2^j + 1\) if \(l\) is greater than or equal to \(2^j\).

By combining these two, one can find the number of integers between \(0\) and \(N\) (inclusive) whose \(j\)-th bit is set.

Hence, the problem has been solved.
Note that since the answer may not fit in \(64\)-bit integer type, you must be cautious when finding the remainder modulo \(998244353\).

Sample code 1 (C++):

#include<bits/stdc++.h>
#define mod 998244353

using namespace std;

long long f(long long j,long long n){
  long long p2=(1ll<<j); // 2^j
  long long k=n/(2*p2);
  long long res=k*p2;
  long long l=n%(2*p2);
  if(l>=p2){
    res+=(l-p2+1);
  }
  return res;
}

int main(){
  long long n,m;
  cin >> n >> m;
  long long res=0;
  for(long long i=0;i<60;i++){
    if(m&(1ll<<i)){
      res+=f(i,n);
      res%=mod;
    }
  }
  cout << res << "\n";
  return 0;
}

Sample code that uses bit operations is as follows.

Sample code 2 (C++):

#include<bits/stdc++.h>
#define mod 998244353

using namespace std;

long long f(long long j,long long n){
  long long res=((n>>(j+1))<<j);
  if(n&(1ll<<j)){
    res+=((n&((1ll<<j)-1))+1);
  }
  return res;
}

int main(){
  long long n,m;
  cin >> n >> m;
  long long res=0;
  for(long long i=0;i<60;i++){
    if(m&(1ll<<i)){
      res+=f(i,n);
      res%=mod;
    }
  }
  cout << res << "\n";
  return 0;
}