题目描述

$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\ &lt\ 998244353 $ を満たす整数 $R$ が一意に定まります。 この $R$ を答えてください。

输入格式

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

$H$ $W$ $S_1$ $S_2$ $\vdots$ $S_H$ $A_1$ $A_2$ $\cdots$ $A_H$

输出格式

答えを出力せよ．

题目大意

有一个 $h$ 行 $w$ 列的棋盘，每个格子内都有一个为 $0$ 或 $1$ 的数字。棋盘的初始状态由 $h$ 个长为 $w$ 的只包含 0 和 1 的字符串 $S_1, S_2, \dots, S_n$ 给定，$S_i$ 的第 $j$ 个字符表示棋盘上从上往下第 $i$ 行、从左往右第 $j$ 列的数字。

给定长为 $h$ 的序列 $a = (a_1, a_2, \dots, a_n)$，Sunke 会重复以下的操作直到对所有 $i$ 有从上往下第 $i$ 行中 $1$ 的数量恰为 $a_i$。

• 随机选择一个格子，翻转该格子中的数（$1$ 变为 $0$，$0$ 变为 $1$）。

请求出 Snuke 执行操作次数的期望在模 $998244353$ 意义下的值。

1 2
01
0

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

提示

制約

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

Sample Explanation 1

操作の様子は以下のようになります． - 確率 $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$ になります．