题目描述

我们有一个$H \times W$的方格网格。你需要用字符$c_{i,j}$来表示从上往下数第$i$行、从左往右数第$j$列$(1 \leq i \leq H, 1 \leq j \leq W)$的方格的颜色：如果$c_{i,j}$为.，方格是白色；如果$c_{i,j}$为#，方格是黑色。

考虑以下操作：

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

给定一个正整数$K$，在操作后，有多少种选择行和列的方式恰好剩下$K$个黑色方格？当且仅当两次选择在行或列的选择上有不同的时候，我们认为这两种选择是不同的。

约束条件

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

输入

输入以以下格式从标准输入给出：

$H$ $W$ $K$
$c_{1,1}c_{1,2}...c_{1,W}$
$c_{2,1}c_{2,2}...c_{2,W}$
$\vdots$
$c_{H,1}c_{H,2}...c_{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