题目描述

给出n行m列的矩阵，矩阵中每个元素是黑色(用#表示)或白色(用.表示)，现在你可以选择若干行及若干列进行染色，染色时，你所选择的行或列将会全部被染成红色。问:有多少种不同的行列选择方案可以使染色后的矩阵中刚好有k个黑色方格。

输入格式

第一行三个整数n,m,k 接下来n行，每行m个字符，表示矩阵

输出格式

一个整数表示方案数

样例 #1

样例输入 #1

2 3 4
..#
###

样例输出 #1

1

样例 #2

样例输入 #2

2 3 2
..#
###

样例输出 #2

5

提示

$1<=n,m<=6,0<=k<=n*m$

对于样例1：

什么都不做是唯一的选择

对于样例2:

第1行和第1列

第1行和第2列

第1行和第3列

第1和第2列

第3列