110003 - 二进制中1的个数

给定 n和m,求:∑_(x=0)^n▒〖popcount(x&m)〗 mod 998244353。 popcount (x) 表示 x 的二进制表示中 1 的个数,比如: 13=(1101)2,所以是 popcount (13)=3。

输入

输入一行包含 2 个正整数n,m(0≤n,m≤2^60−1)。

输出

输出一行答案。

样例

输入

4 3

输出

4

输入

1152921504606846975 1152921504606846975

输出

499791890

提示

样例1中: popcount(0&3)=0, popcount(1&3)=1, popcount(2&3)=1, popcount(3&3)=2, popcount(4&3)=0 答案为:0+1+1+2+0=4

时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题