题目描述

小桃有一个 $h$ 行 $w$ 列的方格网格。给定位于从顶部数第 $i$ 行和从左侧数第 $j$ 列的方格的颜色为字符 $c_{i,j}$：如果 $c_{i,j}$ 是 .，则该方格为白色，如果 $c_{i,j}$ 是 #，则该方格为黑色。

考虑进行以下操作：

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

小桃想知道：给定一个正整数 $k$，有多少种选择行和列的方式使得操作后恰好剩下 $k$ 个黑色方格？当某个选择中只选择了其中的一行或一列时，小桃认为两个选择是不同的。

输入格式：

第一行包含三个整数 $h$, $w$, $k$

接下来 $h$ 行，每行包含一个长度为 $w$ 的字符串，字符串仅包含 . 和 #

输出格式：

输出一个整数表示答案。

2 3 2
..#
###

5

样例1解释

有 $5$ 种方案：

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

2 3 4
..#
###

1

样例2解释

只有一种方案：什么都不选

2 2 3
##
##

0

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

208

数据范围与约定

对于100%的数据，$1 \leq h,w \leq 6$, $1 \leq k \leq h \cdot w$。