问题描述

我们有一个 $H$ 行 $W$ 列的棋盘，每个方格上写着 0 或 1。棋盘的当前状态由 $H$ 个字符串 $S_1, S_2, \cdots, S_H$ 表示：$S_i$ 的第 $j$ 个字符表示位于从上往下数第 $i$ 行、从左往右数第 $j$ 列的方格上的数字。

Snuke 将重复执行以下操作。

• 均匀地随机选择一个方格。然后，翻转该方格上的数字（即将 0 变为 1，将 1 变为 0）。

他特别喜欢一个整数序列 $A=(A_1, A_2, \cdots, A_H)$，所以他会在满足以下条件时终止操作。

• 对于每个 $i$（$1 \leq i \leq H$），从上往下数第 $i$ 行恰好包含 $A_i$ 个 1。

特别地，他可以不进行任何操作。

求 Snuke 执行的操作次数的期望值，对 $998244353$ 取模。

期望值取模 $998244353$ 的定义

可以证明所求的期望值总是一个有理数。此外，在问题的约束条件下，当该值表示为不可约分数 $\\frac{P}{Q}$ 时，也可以证明 $Q \\not \\equiv 0 \\pmod{998244353}$。因此，存在一个唯一的整数 $R$，使得 $R \\times Q \\equiv P \\pmod{998244353}, 0 \\leq R < 998244353$。求出这个 $R$。

约束条件

• $1 \leq H, W \leq 50$
• $S_i$ 是长度为 $W$ 的由 0 和 1 组成的字符串。
• $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 的方格。第一行现在不再包含 1，操作终止。
• 以概率 $1/2$，翻转一个数字为 0 的方格。第一行现在包含两个 1，操作继续。
  • 任意选择一个方格进行翻转。无论翻转哪个方格，第一行现在包含一个 1，操作继续。
    • 以概率 $1/2$，翻转一个数字为 1 的方格。第一行现在不再包含 1，操作终止。
    • 以概率 $1/2$，翻转一个数字为 0 的方格。第一行现在包含两个 1，操作继续。
    • $\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