配点 : $1000$ 点

問題文

$H$ 行 $W$ 列からなる盤面があり，各マスには 0 か 1 が書き込まれています． 盤面の状態は $H$ 個の文字列 $S_1,S_2,\cdots,S_H$ で表され， $S_i$ の $j$ 文字目が，上から $i$ 行目，左から $j$ 列目のマスに書かれている数字を表します．

すぬけくんはこれから，次の操作を繰り返します．

• 一つのマス目を一様ランダムに選ぶ． そして，そのマス目に書かれている値を flip する．（つまり，0 ならば 1 に変え，1 ならば 0 に変える）

ところで，すぬけ君は整数列 $A=(A_1,A_2,\cdots,A_H)$ が大好きです． そのため，以下の条件が満たされた瞬間，操作を終了します．

• すべての $i$ ($1 \leq i \leq H$) について，$i$ 行目にある 1 の個数がちょうど $A_i$ である．

特に，操作を $0$ 回しか行わないこともありえます．

すぬけくんが行う操作回数の期待値を $\text{mod }{998244353}$ で求めてください．

制約

• $1 \leq H,W \leq 50$
• $S_i$ は 0, 1 からなる長さ $W$ の文字列
• $0 \leq A_i \leq W$

入力

入力は以下の形式で標準入力から与えられる．

$H$ $W$

$S_1$

$S_2$

$\vdots$

$S_H$

$A_1$ $A_2$ $\cdots$ $A_H$

出力

答えを出力せよ．

1 2
01
0

3

操作の様子は以下のようになります．

• 確率 $1/2$ で 1 の書かれたマスを flip する．$1$ 行目にある 1 の個数が $0$ になり，操作が終了する．
• 確率 $1/2$ で 0 の書かれたマスを flip する．$1$ 行目にある 1 の個数は $2$ になり，操作は継続する．- いずれかのマスを flip する．flip したマスに依らず，$1$ 行目にある 1 の個数は $1$ になり，操作は継続する．- 確率 $1/2$ で 1 の書かれたマスを flip する．$1$ 行目にある 1 の個数が $0$ になり，操作が終了する．
  • 確率 $1/2$ で 0 の書かれたマスを flip する．$1$ 行目にある 1 の個数は $2$ になり，操作は継続する．
  • $\vdots$
• いずれかのマスを flip する．flip したマスに依らず，$1$ 行目にある 1 の個数は $1$ になり，操作は継続する．
• 確率 $1/2$ で 1 の書かれたマスを flip する．$1$ 行目にある 1 の個数が $0$ になり，操作が終了する．
• 確率 $1/2$ で 0 の書かれたマスを flip する．$1$ 行目にある 1 の個数は $2$ になり，操作は継続する．
• $\vdots$

操作回数の期待値は $3$ になります．

3 3
000
100
110
0 1 2

0

2 2
00
01
1 0

332748127

5 4
1101
0000
0010
0100
1111
1 3 3 2 1

647836743