AT_xmascon20_h Hierarchical Phylogeny

[problemUrl]: https://atcoder.jp/contests/xmascon20/tasks/xmascon20_h 正の整数 $ 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 $ 個ある頂点についてそれらの順番は区別しない．**

入力は以下の形式で標準入力から与えられる． > $ 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\ \le\ N\ \le\ 21 $． ### Sample Explanation 1 この例では，葉にふさわしい集合は $ \{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 $ 頂点の木