AT_tupc2022_o Equidistant Binary String

$ S_{n,m} $ を $ n $ 文字の `0` と $ m $ 文字の `1` からなる長さ $ n+m $ の文字列全体の集合とします。 $ s_1, s_2\in S_{n,m} $ に対して、 $ s_1, s_2 $ の距離 $ d(s_1, s_2) $ を「隣り合った $ 2 $ 文字を入れ替える操作によって文字列 $ s_1 $ を文字列 $ s_2 $ に並び替えるのに必要な最小の操作回数」と定義します。 また、 $ s_1, s_2\in S_{n,m} $ に対して、 $ f(s_1,s_2) $ を次で定めます。 - $ d(s_1,t)=d(s_2,t) $ となる文字列 $ t\in S_{n,m} $ が存在するとき、そのような文字列の中で辞書順最小のものを返す。そのような文字列が存在しないときは $ -1 $ を返す。 --- 正整数 $ n,m $ と文字列 $ T \in S_{n,m} $ が与えられます。 $ f(s_1,s_2)=T $ となるような文字列の組 $ (s_1,s_2)\ (s_1, s_2\in S_{n,m}) $ はいくつありますか？ $ 998244353 $ で割った余りを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ n $ $ m $ $ T $

答えを $ 998244353 $ で割った余りを出力せよ。

### Sample Explanation 1 $ (s_1,s_2)=( $ `0011` $ , $ `0110` $ ),( $ `0011` $ , $ `1001` $ ),( $ `0110` $ , $ `0011` $ ),( $ `1001` , `0011` $ ) $ が条件を満たします。 例えば、 $ (s_1,s_2)=( $ `0011` $ , $ `0110` $ ) $ について、 $ d(s_1, t)=d(s_2, t) $ を満たす $ t\in S_{2,2} $ は `0101` と `1001` がありますが、このうち辞書順で小さいものは `0101` であるため、 $ f(s_1, s_2)= $ `0101` です。 ### Sample Explanation 2 $ (s_1,s_2)=( $ `00001` $ , $ `10000` $ ),( $ `00010` $ , $ `01000` $ ),( $ `01000` $ , $ `00010` $ ),( $ `10000` , `00001` $ ) $ が条件を満たします。 ### Constraints - $ 1\leq n,m\leq 30 $ - $ n,m $ は整数 - $ T\in S_{n,m} $