配点 : $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$ はビットごとの排他的論理和を表します。

制約

• $1 \leq N \leq 200$
• $0 \leq M \lt 2^{30}$
• $0 \leq X \lt 2^{30}$
• 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $X$

出力

答えを出力せよ。

3 3 2

5

問題文中の $2$ つの条件をともに満たす長さ $N$ の整数列 $A$ は、$(0, 0, 2), (0, 1, 3), (1, 1, 2), (2, 2, 2), (2, 3, 3)$ の $5$ 個です。

200 900606388 317329110

788002104