问题描述

有一个 $H$ 行 $W$ 列的网格，其中：

• # 表示黑色格子；
• . 表示白色格子。

现在你可以选择一些行和一些列，并将选中的行或列中的所有格子涂成红色。

选择的行和列可以为空，也就是说你可以一行都不选，也可以一列都不选。

涂色完成后，红色格子不再算作黑色格子。

请你计算一共有多少种不同的选择方法，使得涂色完成后，网格中恰好剩下 $K$ 个黑色格子。

注意：选择哪些行和哪些列不同，就算作不同的方案。

输入格式

第一行输入三个整数 $H,W,K$，分别表示网格的行数、列数以及涂色完成后需要剩下的黑色格子数量。

接下来输入 $H$ 行，每行包含一个长度为 $W$ 的字符串，表示网格。

其中：

• # 表示黑色格子；
• . 表示白色格子。

输出格式

输出一个整数，表示满足条件的不同选择方法数量。

样例输入 1

2 3 2
..#
###

样例输出 1

5

样例输入 2

2 3 4
..#
###

样例输出 2

1

样例输入 3

2 2 3
##
##

样例输出 3

0

样例输入 4

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

样例输出 4

208

说明

每一种选择都由两部分组成：

1. 选择哪些行进行涂色；
2. 选择哪些列进行涂色。

例如，选择第 $1$ 行和第 $3$ 列，与只选择第 $1$ 行，是两种不同的方案。

评测数据规模

对于所有数据：

$1 \le H,W \le 6$

$1 \le K \le H\times W$