AT_abc173_c.[ABC173C] H and V

有一个由 $H$ 行 $W$ 列组成的网格。第 $i$ 行第 $j$ 列的格子的颜色由字符 $c_{i,j}$ 给出，当 $c_{i,j}$ 为 . 时表示白色，为 # 时表示黑色。

现在要进行如下操作：

• 可以选择若干行（也可以一行都不选），再选择若干列（也可以一列都不选）。然后，将被选中的所有行和所有列中的格子全部涂成红色。

给定一个正整数 $K$，问有多少种选择行和列的方法，使得操作后网格中恰好剩下 $K$ 个黑色格子。这里，如果存在某一行或某一列只在其中一种选择中被选中，则认为这两种选择不同。

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

$H$ $W$ $K$
$c_{1,1}c_{1,2}\ldots c_{1,W}$
$c_{2,1}c_{2,2}\ldots c_{2,W}$
$\vdots$
$c_{H,1}c_{H,2}\ldots c_{H,W}$

输出满足条件的行和列的选择方法数。

限制条件

• $1 \leq H, W \leq 6$
• $1 \leq K \leq HW$
• $c_{i,j}$ 仅为 . 或 #

样例解释 1

以下 $5$ 种选择满足条件：

• 第 $1$ 行和第 $1$ 列
• 第 $1$ 行和第 $2$ 列
• 第 $1$ 行和第 $3$ 列
• 第 $1$ 列和第 $2$ 列
• 第 $3$ 列

样例解释 2

什么都不选这一种选择满足条件。

由 ChatGPT 4.1 翻译