问题陈述

有一个由 $H \times W$ 个格子组成的网格。用 $(i, j)$ 表示从上往下第 $i$ 行、从左往右第 $j$ 列的格子。

若 $S_{i,j}$ 为 .，则格子 $(i, j)$ 为空；若为 #，则为障碍。

请计算从某个空格子出发，进行 $K$ 次移动到相邻格子（上、下、左、右）的方案数，要求不经过障碍格子，且不重复访问同一个格子。

具体来说，计算满足以下条件的长度为 $K+1$ 的序列 $((i_0, j_0), (i_1, j_1), \dots, (i_K, j_K))$ 的数量。

• 对于每个 $0 \leq k \leq K$，都有 $1 \leq i_k \leq H$，$1 \leq j_k \leq W$，且 $S_{i_k, j_k}$ 为 .。
• 对于每个 $0 \leq k \leq K-1$，都有 $|i_{k+1} - i_k| + |j_{k+1} - j_k| = 1$。
• 对于每个 $0 \leq k < l \leq K$，都有 $(i_k, j_k) \neq (i_l, j_l)$。

约束

• $1 \leq H, W \leq 10$
• $1 \leq K \leq 11$
• $H$、$W$、$K$ 为整数。
• 每个 $S_{i,j}$ 为 . 或 #。
• 至少有一个空格子。

输入

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

$H W K$ $S_{1,1}S_{1,2}\dots S_{1,W}$ $S_{2,1}S_{2,2}\dots S_{2,W}$ $\vdots$ $S_{H,1}S_{H,2}\dots S_{H,W}$

输出

输出答案。

样例输入 1

2 2 2
.#
..

样例输出 1

2

可能的路径有以下两条：

• $(1,1) \rightarrow (2,1) \rightarrow (2,2)$
• $(2,2) \rightarrow (2,1) \rightarrow (1,1)$

样例输入 2

2 3 1
.#.
#.#

样例输出 2

0

样例输入 3

10 10 11
....#..#..
.#.....##.
..#...##..
...#......
......##..
..#......#
#........#
..##......
.###....#.
...#.....#

样例输出 3

218070