配点 : 500 点
問題文
正整数 N, M が与えられます。
長さ N の正整数列 A=(A1, A2, …, AN) であって、以下の条件を満たすものの個数を 998244353 で割った余りを求めてください。
- 1≤A1<A2<⋯<AN≤M
- Bi=A1⊕A2⊕⋯⊕Ai としたとき、 B1<B2<⋯<BN
ただしここで、 ⊕ はビット単位 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$ である。
例えば、3 \oplus 5 = 6 となります (二進表記すると: 011 \oplus 101 = 110)。
一般に 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≤N≤M<260
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
N M
出力
答えを出力してください。
2 4
5
例えば (A1, A2)=(1, 3) とすると A1<A2 であり、B1=A1=1, B2=A1⊕A2=2 より B1<B2 が成り立つので条件を満たします。
この他には (A1, A2)=(1, 2), (1, 4), (2, 4), (3, 4) が条件を満たします。
4 4
0
10 123456789
205695670
