题目描述

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

考虑进行以下操作：

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

给定一个正整数 $K$。有多少种行和列的选择方式，可以使得操作后恰好剩下 $K$ 个黑色方格？这里，如果两种选择方式在选择的行或列上有任何不同，就认为是不同的选择。

输入格式

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

$H$ $W$ $K$

$c_{1,1}$, $c_{1,2}$ $\ldots$ $c_{1,W}$

$c_{2,1}$, $c_{2,2}$ $\ldots$ $c_{2,W}$

$\vdots$

$c_{H,1}$, $c_{H,2}$ $\ldots$ $c_{H,W}$

输出格式

输出一个整数，表示满足条件的行和列选择方式的数量。

样例

2 3 2
..#
###

5

2 3 4
..#
###

1

2 2 3
##
##

0

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

208

样例解释

【 样例说明1】
以下五种选择满足条件：

• 第1行和第1列
• 第1行和第2列
• 第1行和第3列
• 第1列和第2列
• 第3列
  【样例说明2】
  只有一种选择满足条件，即什么都不选。

  数据范围

• $1 ≤ H, W ≤ 6$
• $1 ≤ K ≤ HW$
• $c_{i,j}$ 是 '.' 或 '#'。$

来源

• AtCoder ABC173C