题目描述

有一个由 $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<998244353$。请输出这个 $R$。

输入格式

输入按以下格式从标准输入读入。

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

输出格式

请输出答案。

样例 1

输入

1 2
01
0

输出

3

样例 2

输入

3 3
000
100
110
0 1 2

输出

0

样例 3

输入

2 2
00
01
1 0

输出

332748127

样例 4

输入

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$

样例解释 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 翻译