H 与 V

题目描述

有一个由 $H$ 行 $W$ 列的格子组成的方格纸。从上数第 $i$ 行、从左数第 $j$ 列 $(1 \leq i \leq H, 1 \leq j \leq W)$ 的格子的颜色由字符 $c_{i,j}$ 给出,$c_{i,j}$ 为 . 时是白色,为 # 时是黑色。

考虑进行以下操作:

• 选择若干行(可以是 $0$ 行),再选择若干列(可以是 $0$ 列)。然后把所选行中包含的格子和所选列中包含的格子全部涂成红色。

给定正整数 $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}$
$:$
$c_{H,1}c_{H,2} \ldots c_{H,W}$

输出格式

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

样例

2 3 2
..#
###

5

以下 $5$ 种选择方法满足条件:

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

2 3 4
..#
###

1

什么也不选的 $1$ 种选择方法满足条件。

2 2 3
##
##

0

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

208

数据范围

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