/ 
Time Limit: 6 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
数列 a_0, a_1, a_2, \dots の一般項 a_n を次のように定義します。
整数 N が与えられます。m\text{ AND }N = m を満たす全ての非負整数 m に対する a_m の総和を 998244353 で割った余りを求めてください。(\text{AND} はビット単位 AND)
ビット単位 AND とは？
整数 A,B のビット単位 AND、A\text{ AND }B は以下のように定義されます。・A\text{ AND }B を二進表記した際の 2^k (k \geq 0) の位の数は、A,B を二進表記した際の 2^k の位の数のうち両方が 1 であれば 1、そうでなければ 0 である。
制約
- 1 \leq K \leq 5 \times 10^4
- 0 \leq N \leq 10^{18}
- N, K は整数
入力
入力は以下の形式で標準入力から与えられる。
K N
出力
答えを出力せよ。
入力例 1
2 6
出力例 1
21
数列の各項を a_0 から順に並べると 1, 1, 2, 3, 5, 8, 13, 21, \dots になります。
6 \text{ AND } m = m であるような非負整数は 0, 2, 4, 6 の 4 個なので、答えは 1 + 2 + 5 + 13 = 21 になります。
入力例 2
2 8
出力例 2
35
入力例 3
1 123456789
出力例 3
65536
入力例 4
300 20230429
出力例 4
125461938
入力例 5
42923 999999999558876113
出力例 5
300300300
Score : 600 points
Problem Statement
We define the general term a_n of a sequence a_0, a_1, a_2, \dots by:
Given an integer N, find the sum, modulo 998244353, of a_m over all non-negative integers m such that m\text{ AND }N = m. (\text{AND} denotes the bitwise AND.)
What is bitwise AND?
The bitwise AND of non-negative integers A and B, A\text{ AND }B, is defined as follows.・When A\text{ AND }B is written in binary, its 2^ks place (k \geq 0) is 1 if 2^ks places of A and B are both 1, and 0 otherwise.
Constraints
- 1 \leq K \leq 5 \times 10^4
- 0 \leq N \leq 10^{18}
- N and K are integers.
Input
The input is given from Standard Input in the following format:
K N
Output
Print the answer.
Sample Input 1
2 6
Sample Output 1
21
a_0 and succeeding terms are 1, 1, 2, 3, 5, 8, 13, 21, \dots. Four non-negative integers, 0, 2, 4, and 6, satisfy 6 \text{ AND } m = m, so the answer is 1 + 2 + 5 + 13 = 21.
Sample Input 2
2 8
Sample Output 2
35
Sample Input 3
1 123456789
Sample Output 3
65536
Sample Input 4
300 20230429
Sample Output 4
125461938
Sample Input 5
42923 999999999558876113
Sample Output 5
300300300