問題文

$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$ で割った余りを求めてください。

制約

• $1\leq n,m\leq 30$
• $n,m$ は整数
• $T\in S_{n,m}$

入力例 1Copy

2 2
0101

出力例 1Copy

4

$(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 です。

入力例 2Copy

4 1
00100

出力例 2Copy

4

$(s_1,s_2)=($ 00001 $,$ 10000 $),($00010 $,$ 01000 $),($ 01000 $,$ 00010 $),($ 10000 , 00001 $)$ が条件を満たします。

入力例 3Copy

3 3
111000

出力例 3Copy

0

入力例 4Copy

6 4
0001111000

出力例 4Copy

1254