問題文

$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}$ で求めてください．

期待値 $\\text{mod }{998244353}$ の定義

求める期待値は必ず有理数になることが証明できます。 また、この問題の制約のもとでは、その値を既約分数 $\\frac{P}{Q}$ で表した時、$Q \\not \\equiv 0 \\pmod{998244353}$ となることも証明できます。 よって、$R \\times Q \\equiv P \\pmod{998244353}, 0 \\leq R < 998244353$ を満たす整数 $R$ が一意に定まります。 この $R$ を答えてください。

制約

• $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

1 2
01
0

出力例 1

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$

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

---

入力例 2

3 3
000
100
110
0 1 2

出力例 2

0

---

入力例 3

2 2
00
01
1 0

出力例 3

332748127

---

入力例 4

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

出力例 4

647836743