/ 
Time Limit: 6 sec / Memory Limit: 1024 MB
配点 : 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