网格涂色

题目描述

我们有一个 $H \times W$ 的网格，每个格子都被涂成黑色或白色。

给定字符串 $A_1,A_2,\ldots,A_H$，表示初始时每个格子的颜色。其中，$A_i$ 的第 $j$ 个字符表示格子 $(i,j)$ 的颜色：

• . 表示白色；
• # 表示黑色。

规定可以进行以下四种操作：

1. 选择一行，然后将该行中的所有格子涂成白色。
2. 选择一行，然后将该行中的所有格子涂成黑色。
3. 选择一列，然后将该列中的所有格子涂成白色。
4. 选择一列，然后将该列中的所有格子涂成黑色。

在所有 $2^{HW}$ 种可能的网格涂色方案中，问有多少种不同的方案可以通过从初始状态开始，以任意顺序执行任意次数上述操作得到？

由于答案可能很大，请将结果对 $998244353$ 取模。

输入格式

第一行输入两个整数 $H,W$。

接下来 $H$ 行，每行输入一个长度为 $W$ 的字符串，依次表示 $A_1,A_2,\ldots,A_H$。

输出格式

输出一行一个整数，表示可以得到的不同涂色方案数量，对 $998244353$ 取模。

输入输出样例 #1

输入 #1

2 2
#.
.#

输出 #1

15

输入输出样例 #2

输入 #2

3 3
...
...
...

输出 #2

230

输入输出样例 #3

输入 #3

2 4
#...
...#

输出 #3

150

输入输出样例 #4

输入 #4

6 7
.......
.......
.#.....
..#....
.#.#...
.......

输出 #4

203949910

说明/提示

对于所有测试数据，满足：

• $1 \le H,W \le 10$；
• $H,W$ 均为正整数；
• $|A_i|=W\ (1 \le i \le H)$；
• $A_i$ 仅由 . 和 # 组成。