配点 : 100 点
进行生物学研究的鳗鱼,想要计算某些生物分类的系统树数量。在鳗鱼的研究中,已经列出了一些可以被视为不再细分的物种集合,以及作为系统树制作对象的集合。当然,鳗鱼并不擅长计数也不会影响它,但今天由于紧急情况,它必须非常快速地进行计数。
問題文
正整数 N 。\{0, \ldots, N - 1\} 的非空子集各自,“是否适合作为叶子”以及“是否适合作为根”已被确定。
在带根树的各顶点上, \{0, \ldots, N - 1\} 的非空子集 1 个被写作标签,且满足以下所有条件的数量除以 998244353 取余数:
- 每个顶点的子节点为 0 件或 2 。
- 子节点为 0 个顶点的标签适合作为叶子。
- 子节点为 2 个顶点满足以下条件:该顶点的标签为 A,子节点的标签为 B, C 时,B \cup C = A 和 B \cap C = \emptyset.
- 根的标签适合作为根。
但是,对于有 2 个子节点的顶点,它们的顺序不区分。
制約
- 1 \le N \le 21.
入力
输入是按以下格式从标准输入给出的。
N L R
L 是
您也可以写 0 和
按字典顺序比较 1 组成的长度 2^N 是一个字符串,每个 A \subseteq \{0, \ldots, N - 1\} ,
定义\left(1 + \sum_{a\in A} 2^a\right) 第一个字符是 A 是
在是否适合作为叶子时, 1,否则 0 。但是,1 个字符(开头)必须满足条件。 0 是。
R 是
您也可以写 0 和
按字典顺序比较 1 组成的长度 2^N 是一个字符串,每个 A \subseteq \{0, \ldots, N - 1\} ,
定义\left(1 + \sum_{a\in A} 2^a\right) 第一个字符是 A 是
在是否适合作为根时, 1,否则 0 。但是,1 个字符(开头)必须满足条件。 0 是。
出力
满足条件的标记根树的数量为 998244353 后的余数。 对于
入力例 1
3 01110111 00000101
出力例 1
4
。 在这个例子中,适合作为叶子的集合有 \{0\}, \{1\}, \{0, 1\}, \{0, 2\}, \{1, 2\}, \{0, 1, 2\} 可以得到第 6 个,适合作为根的集合有 \{0, 2\}, \{0, 1, 2\} 可以得到第 2 个。满足条件的标记根树如下 4 个:
- 根的标签是 \{0, 2\} 是 1 顶点树 在
- 根的标签是 \{0, 1, 2\} 是 1 顶点树 在
- 根的标签是 \{0, 1, 2\} 并且,其子节点的标签是 \{0\}, \{1, 2\} 是 3 顶点树 在
- 根的标签是 \{0, 1, 2\} 并且,其子节点的标签是 \{1\}, \{0, 2\} 是 3 顶点树 在
入力例 2
5 00000001000101100001011001101000 00000000000000010000000100010111
出力例 2
0
入力例 3
6 0111001111111111111111101111111111111111111110111111111111111110 0111001111111111111111111111111111110111111111111001000000010001
出力例 3
2020