/ 
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
下記の 2 つの条件をともに満たす長さ N の整数列 A = (A_1, A_2, \ldots, A_N) の個数を 998244353 で割ったあまりを出力してください。
- 0 \leq A_1 \leq A_2 \leq \cdots \leq A_N \leq M
- A_1 \oplus A_2 \oplus \cdots \oplus A_N = X
ここで、\oplus はビットごとの排他的論理和を表します。
ビットごとの排他的論理和とは？
非負整数 A, B のビットごとの排他的論理和 A \oplus B は、以下のように定義されます。- A \oplus B を二進表記した際の 2^k (k \geq 0) の位の数は、A, B を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。
制約
- 1 \leq N \leq 200
- 0 \leq M \lt 2^{30}
- 0 \leq X \lt 2^{30}
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M X
出力
答えを出力せよ。
入力例 1
3 3 2
出力例 1
5
問題文中の 2 つの条件をともに満たす長さ N の整数列 A は、(0, 0, 2), (0, 1, 3), (1, 1, 2), (2, 2, 2), (2, 3, 3) の 5 個です。
入力例 2
200 900606388 317329110
出力例 2
788002104
Score : 600 points
Problem Statement
Print the number of integer sequences of length N, A = (A_1, A_2, \ldots, A_N), that satisfy both of the following conditions, modulo 998244353.
- 0 \leq A_1 \leq A_2 \leq \cdots \leq A_N \leq M
- A_1 \oplus A_2 \oplus \cdots \oplus A_N = X
Here, \oplus denotes bitwise XOR.
What is bitwise XOR?
The bitwise XOR of non-negative integers A and B, A \oplus B, is defined as follows.
- When A \oplus B is written in binary, the k-th lowest bit (k \geq 0) is 1 if exactly one of the k-th lowest bits of A and B is 1, and 0 otherwise.
Constraints
- 1 \leq N \leq 200
- 0 \leq M \lt 2^{30}
- 0 \leq X \lt 2^{30}
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N M X
Output
Print the answer.
Sample Input 1
3 3 2
Sample Output 1
5
Here are the five sequences of length N that satisfy both conditions in the statement: (0, 0, 2), (0, 1, 3), (1, 1, 2), (2, 2, 2), (2, 3, 3).
Sample Input 2
200 900606388 317329110
Sample Output 2
788002104