/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 500 点
問題文
正整数 N,\ M が与えられます。
長さ N の正整数列 A=(A_1,\ A_2,\ \dots,\ A_N) であって、以下の条件を満たすものの個数を 998244353 で割った余りを求めてください。
- 1 \leq A_1 < A_2 < \dots < A_N \leq M
- B_i = A_1 \oplus A_2 \oplus \dots \oplus A_i としたとき、 B_1 < B_2 < \dots < B_N
ただしここで、 \oplus はビット単位 \mathrm{XOR} 演算を表します。
ビット単位 \mathrm{XOR} 演算とは
非負整数 A, B のビット単位 \mathrm{XOR} 、A \oplus B は、以下のように定義されます。
- A \oplus B を二進表記した際の 2^k (k \geq 0) の位の数は、A, B を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。
一般に k 個の非負整数 p_1, p_2, p_3, \dots, p_k のビット単位 \mathrm{XOR} は (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k) と定義され、これは p_1, p_2, p_3, \dots, p_k の順番によらないことが証明できます。
制約
- 1 \leq N \leq M < 2^{60}
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
N M
出力
答えを出力してください。
入力例 1
2 4
出力例 1
5
例えば (A_1,\ A_2)=(1,\ 3) とすると A_1 < A_2 であり、B_1=A_1=1,\ B_2=A_1\oplus A_2=2 より B_1 < B_2 が成り立つので条件を満たします。
この他には (A_1,\ A_2)=(1,\ 2),\ (1,\ 4),\ (2,\ 4),\ (3,\ 4) が条件を満たします。
入力例 2
4 4
出力例 2
0
入力例 3
10 123456789
出力例 3
205695670
Score : 500 points
Problem Statement
You are given positive integers N and M.
Find the number of sequences A=(A_1,\ A_2,\ \dots,\ A_N) of N positive integers that satisfy the following conditions, modulo 998244353.
- 1 \leq A_1 < A_2 < \dots < A_N \leq M.
- B_1 < B_2 < \dots < B_N, where B_i = A_1 \oplus A_2 \oplus \dots \oplus A_i.
Here, \oplus denotes bitwise \mathrm{XOR}.
What is bitwise \mathrm{XOR}?
The bitwise \mathrm{XOR} of non-negative integers A and B, A \oplus B, is defined as follows:
- When A \oplus B is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if exactly one of A and B is 1, and 0 otherwise.
Generally, the bitwise \mathrm{XOR} of k non-negative integers p_1, p_2, p_3, \dots, p_k is defined as (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k). We can prove that this value does not depend on the order of p_1, p_2, p_3, \dots, p_k.
Constraints
- 1 \leq N \leq M < 2^{60}
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M
Output
Print the answer.
Sample Input 1
2 4
Sample Output 1
5
For example, (A_1,\ A_2)=(1,\ 3) counts, since A_1 < A_2 and B_1 < B_2 where B_1=A_1=1,\ B_2=A_1\oplus A_2=2.
The other pairs that count are (A_1,\ A_2)=(1,\ 2),\ (1,\ 4),\ (2,\ 4),\ (3,\ 4).
Sample Input 2
4 4
Sample Output 2
0
Sample Input 3
10 123456789
Sample Output 3
205695670