C - H和V

分数：300分

问题描述

给出一个$H$行$W$列的方块网络。方块网格中从上到下的第$i$行、从左到右的第$j$列（$1 \leq i \leq H, 1 \leq j \leq W$）的颜色用字符$c_{i,j}$来表示：如果$c_{i,j}$为.，那么方块为白色；如果$c_{i,j}$为#，那么方块为黑色。

考虑以下操作：

• 选择一些行（可以为零个）和一些列（可以为零个）。然后将选择的行和列中的所有方块涂成红色。

给出一个正整数$K$。在进行上述操作后，恰好还剩下$K$个黑色方块的行和列的选择有多少种？在这里，当两个选择只有一个选择中有行或列时，我们认为它们是不同的选择。

约束

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

输入

从标准输入读入数据，格式如下：

$H$ $W$ $K$

$c_{1,1}c_{1,2}...c_{1,W}$

$c_{2,1}c_{2,2}...c_{2,W}$

$:$

$c_{H,1}c_{H,2}...c_{H,W}$

输出

输出一个整数，表示满足条件的行和列的选择数。

2 3 2
..#
###

5

如下所示，有五种选择满足条件。

• 第一行和第一列
• 第一行和第二列
• 第一行和第三列
• 第一列和第二列
• 第三列

2 3 4
..#
###

1

只有一种选择不选择任何行和列满足条件。

2 2 3
##
##

0

6 6 8
..##..
.#..#.
#....#
######
#....#
#....#

208