问题描述

给定一个 $H$ 行 $W$ 列的网格，令 $(i,j)$ 表示从上到下第 $i$ 行、从左到右第 $j$ 列的格子。

当 $S_{i,j}$ 为 . 时，该格子为空地；当 $S_{i,j}$ 为 # 时，该格子为障碍物。

请统计满足以下条件的路径数量：

一条路径表示为长度为 $K+1$ 的序列：

满足：

• 对于每个 $0 \le k \le K$，都有$$1\le i_k\le H,\quad 1\le j_k\le W$$ 且 $S_{i_k,j_k}=\texttt{'.'}$；
• 对于每个 $0\le k<K$，都有$$|i_{k+1}-i_k|+|j_{k+1}-j_k|=1$$ 即每次只能向上、下、左、右移动一步；
• 对于任意 $0\le k<l\le K$，都有$$(i_k,j_k)\ne(i_l,j_l)$$ 即路径中不能重复经过同一个格子。

请输出满足条件的路径总数。

输入格式

输入从标准输入读入，格式如下：

$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

样例输入2

2 3 1
.#.
#.#

样例输出2

0

样例输入3

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

样例输出3

218070

说明

对于样例 1，共有两种合法路径：

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

评测数据规模

• $1\le H,W\le 10$
• $1\le K\le 11$
• $H,W,K$ 均为整数
• 每个 $S_{i,j}$ 都是 . 或 #
• 网格中至少存在一个空地格子