题目描述

下記の $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$ である。

例えば、$3\ \oplus\ 5\ =\ 6$ となります (二進表記すると: $011\ \oplus\ 101\ =\ 110$)。

输入格式

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

$N$ $M$ $X$

输出格式

答えを出力せよ。

题目大意

给定 $N$，$M$，$X$ ，询问有多少个长度为 $N$ 的非负整数序列满足以下条件：

$0\le A_1\le A_2\le ...\le A_N\le M$

$A_1\oplus A_2\oplus...\oplus A_N=X$

其中 $\oplus$ 是异或操作，答案对 $998244353$ 取模。( $1\le N\le 200$，$0\le M\lt 2^{30}$ ，$0\le X\lt 2^{30}$ )

3 3 2

5

200 900606388 317329110

788002104

提示

制約

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

Sample Explanation 1

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