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 翻译