Problem Description

Given a positive integer $N$, for each non-empty subset of $\{0, \ldots, N - 1\}$, it is determined whether it is "suitable for leaves" or not, and whether it is "suitable for roots" or not.

Find the number of rooted trees where each vertex is labeled with a non-empty subset of $\{0, \ldots, N - 1}$, and all of the following conditions are satisfied, modulo $998244353$:

• Each vertex has either $0$ or $2$ children.
• The label of a vertex with $0$ children is suitable for leaves.
• For a vertex with $2$ children, let the label of the vertex be $A$, and the labels of its children be $B$ and $C$. Then, $B \cup C = A$ and $B \cap C = \emptyset$.
• The label of the root is suitable for roots.

Note that the order of children of a vertex with $2$ children is not distinguished.

Input Format

The input is given from the standard input in the following format:

$N$ $L$ $R$

$L$ is a string of length $2^N$ consisting of 0 and 1. For each subset $A \subseteq \{0, \ldots, N - 1\}$, the $\left(1 + \sum_{a \in A} 2^a\right)$-th character is 1 if $A$ is suitable for leaves, and 0 otherwise. The first character (head) is always 0.

$R$ is a string of length $2^N$ consisting of 0 and 1. For each subset $A \subseteq \{0, \ldots, N - 1\}$, the $\left(1 + \sum_{a \in A} 2^a\right)$-th character is 1 if $A$ is suitable for roots, and 0 otherwise. The first character (head) is always 0.

Output Format

Output the number of labeled rooted trees satisfying the conditions, modulo $998244353$.

Sample Input and Output

Sample Input #1

3
01110111
00000101

Sample Output #1

4

Sample Input #2

5
00000001000101100001011001101000
00000000000000010000000100010111

Sample Output #2

0

Sample Input #3

6
0111001111111111111111101111111111111111111110111111111111111110
0111001111111111111111111111111111110111111111111001000000010001

Sample Output #3

2020

Notes/Hints

Constraints

• $1 \le N \le 21$.

Sample Explanation 1

In this example, the sets suitable for leaves are $\{0\}$, $\{1\}$, $\{0, 1\}$, $\{0, 2\}$, $\{1, 2\}$, $\{0, 1, 2\}$, totaling 6 sets. The sets suitable for roots are $\{0, 2\}$, $\{0, 1, 2\}$, totaling 2 sets. The labeled rooted trees satisfying the conditions are the following 4:

• A tree with 1 vertex where the root label is $\{0, 2\}$.
• A tree with 1 vertex where the root label is $\{0, 1, 2\}$.
• A tree with 3 vertices where the root label is $\{0, 1, 2\}$ and the labels of its children are $\{0\}$ and $\{1, 2\}$.
• A tree with 3 vertices where the root label is $\{0, 1, 2\}$ and the labels of its children are $\{1\}$ and $\{0, 2\}$.

见题面 Input 部分

见题面 Output 部分