题目描述

小高有一个 $H$ 行 $W$ 列的网格。第 $i$ 行第 $j$ 列的方格颜色由字符 $c_{i,j}$ 给出：如果 $c_{i,j}$ 是 '.'，则为白色；如果是 '#'，则为黑色。

考虑进行以下操作：

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

给定一个正整数 $K$。有多少种行和列的选择方式，可以使得操作后恰好剩下 $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

说明/提示

样例 1 解释

以下五种选择满足条件：

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

样例 2 解释

只有一种选择满足条件，即什么都不选。

数据范围

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