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 翻译