AT_arc136_f [ARC136F] Flip Cells

有一个由 $H$ 行 $W$ 列组成的棋盘，每个格子上写有 `0` 或 `1`。棋盘的状态由 $H$ 个字符串 $S_1,S_2,\cdots,S_H$ 表示，第 $i$ 个字符串 $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$。 特别地，也有可能一次操作都不进行。 请你求出すぬけ君所需操作次数的期望值，结果对 $998244353$ 取模。 期望值 $\bmod\ 998244353$ 的定义 可以证明，所求的期望值一定是有理数。在本题的约束下，将其表示为最简分数 $\frac{P}{Q}$ 时，$Q\not\equiv 0\pmod{998244353}$ 也成立。因此，存在唯一的整数 $R$ 满足 $R\times Q\equiv P\pmod{998244353},\ 0\leq R

输入按以下格式从标准输入读入。 > $H$ $W$ > $S_1$ > $S_2$ > $\vdots$ > $S_H$ > $A_1$ $A_2$ $\cdots$ $A_H$

请输出答案。

### 约束条件 - $1\leq H,W\leq 50$ - $S_i$ 是由 `0` 和 `1` 组成的长度为 $W$ 的字符串 - $0\leq A_i\leq W$ ### 样例解释 1 操作过程如下： - 以概率 $1/2$ flip 一个写有 `1` 的格子。第 $1$ 行中 `1` 的个数变为 $0$，操作结束。 - 以概率 $1/2$ flip 一个写有 `0` 的格子。第 $1$ 行中 `1` 的个数变为 $2$，操作继续。 - 无论 flip 哪个格子，第 $1$ 行中 `1` 的个数都会变为 $1$，操作继续。 - 以概率 $1/2$ flip 一个写有 `1` 的格子。第 $1$ 行中 `1` 的个数变为 $0$，操作结束。 - 以概率 $1/2$ flip 一个写有 `0` 的格子。第 $1$ 行中 `1` 的个数变为 $2$，操作继续。 - $\vdots$ - 操作次数的期望值为 $3$。 由 ChatGPT 4.1 翻译