题目描述

给你一个 $N$ 行 $M$ 列的字符矩形，其中不是 . 就是 #。现在你可以任选行与列，将其去掉，使得剩下的行列中，包括的 # 有且只有 $K$ 个，求有多少种不同的选择方式。

输入格式

输入格式如下：

$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}$

输出格式

输出满足条件的选择方案数。

样例 #1

样例输入 #1

2 3 2
..#
###

样例输出 #1

5

• 选第一行第一列
• 选第一行第二列
• 选第一行第三列
• 选第一列第二列
• 选第三列

样例 #2

样例输入 #2

2 3 4
..#
###

样例输出 #2

1

只有一种选择，就是所有行列都不选

样例 #3

样例输入 #3

2 2 3
##
##

样例输出 #3

0

样例 #4

样例输入 #4

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

样例输出 #4

208

提示

对于 $100\%$ 的数据：

• $1\ \leq\ H,\ W\ \leq\ 6$
• $1\ \leq\ K\ \leq\ HW$
• $c_{i,j}$ 只包含 $.$ 和 $\#$