无名计数问题

题目描述

求同时满足以下两个条件的长为 $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$ 写成二进制时,第 $k$ 低位($k \geq 0$)在 $A$ 和 $B$ 的二进制表示中恰好一个的第 $k$ 低位为 $1$ 时为 $1$,否则为 $0$。

例如,$3 \oplus 5 = 6$(二进制:$011 \oplus 101 = 110$)。

输入格式

输入按以下格式从标准输入给出:

$N$ $M$ $X$

输出格式

输出答案。

样例

3 3 2

5

满足题述两个条件的长为 $N$ 的序列有以下 5 个:$(0, 0, 2), (0, 1, 3), (1, 1, 2), (2, 2, 2), (2, 3, 3)$。

200 900606388 317329110

788002104

数据范围

• $1 \leq N \leq 200$
• $0 \leq M \lt 2^{30}$
• $0 \leq X \lt 2^{30}$
• 输入中的所有值均为整数。