题目描述

给你一个 $N$ 行 $M$ 列的字符矩形，其中每个字符要么是 . 要么是 #。

你可以选择去掉若干行和若干列，问有多少种方案使得剩下的 # 的个数恰好是 $K$ 个？

输入格式

第一行输入三个空格隔开的正整数 $N,M,K$

接下来 $N$ 行每行输入 $M$ 个字符。

输出格式

输出满足条件的方案数

2 3 2
..#
###

5

2 3 4
..#
###

1

2 2 3
##
##

0

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

208

样例 1 解释

以下五个选项符合条件。

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

样例 2 解释

只有一种方案可以满足有恰好 $K$ 个 #，那就是不去掉任何一行与任何一列。

数据范围

• $1 \leq N, M \leq 6$
• $1 \leq K \leq N\times M$
• $c_{i,j}$ 是 . 或 #。