AT_xmascon20_h Hierarchical Phylogeny

给定一个正整数 $N$。对于 $\{0,\ldots,N-1\}$ 的每一个非空子集，都已经确定了它是否“适合作为叶子”以及是否“适合作为根”。 请计算满足以下所有条件的有根树的数量（每个顶点都标记有 $\{0,\ldots,N-1\}$ 的一个非空子集），并将答案对 $998244353$ 取模： - 每个顶点的子节点数要么为 $0$，要么为 $2$。 - 子节点数为 $0$ 的顶点，其标签必须是适合作为叶子的集合。 - 子节点数为 $2$ 的顶点，设该顶点的标签为 $A$，两个子节点的标签为 $B, C$，则必须满足 $B \cup C = A$ 且 $B \cap C = \emptyset$。 - 根节点的标签必须是适合作为根的集合。 **注意，对于有两个子节点的顶点，这两个子节点的顺序不区分。**

输入通过标准输入给出，格式如下： > $N$ $L$ $R$ $L$ 是一个由 `0` 和 `1` 组成的长度为 $2^N$ 的字符串。对于每个 $A \subseteq \{0,\ldots,N-1\}$，第 $\left(1+\sum_{a\in A} 2^a\right)$ 个字符为 `1` 表示 $A$ 适合作为叶子，否则为 `0`。其中第 $1$ 个字符（开头）一定为 `0`。 $R$ 是一个由 `0` 和 `1` 组成的长度为 $2^N$ 的字符串。对于每个 $A \subseteq \{0,\ldots,N-1\}$，第 $\left(1+\sum_{a\in A} 2^a\right)$ 个字符为 `1` 表示 $A$ 适合作为根，否则为 `0`。其中第 $1$ 个字符（开头）一定为 `0`。

输出满足条件的有根树的数量，对 $998244353$ 取模。

## 限制 - $1 \leq N \leq 21$。 ## 样例解释 1 在本例中，适合作为叶子的集合有 $\{0\},\{1\},\{0,1\},\{0,2\},\{1,2\},\{0,1,2\}$ 共 $6$ 个，适合作为根的集合有 $\{0,2\},\{0,1,2\}$ 共 $2$ 个。满足条件的有根树共有 $4$ 个： - 根标签为 $\{0,2\}$ 的单节点树 - 根标签为 $\{0,1,2\}$ 的单节点树 - 根标签为 $\{0,1,2\}$，其子节点标签为 $\{0\},\{1,2\}$ 的三节点树 - 根标签为 $\{0,1,2\}$，其子节点标签为 $\{1\},\{0,2\}$ 的三节点树 由 ChatGPT 4.1 翻译