有一个 $H\times W$ 的方格图，字符 . 表示可进入，字符 # 表示障碍。小珅可以任选一个可进入格作为起点，之后每一步移动到上下左右相邻的可进入格。

一条长度为 $K$ 的路线包含起点和之后的 $K$ 次移动，并且任何格子都不能重复经过。请统计所有不同路线的数量。起点不同或任意一步经过的格子不同，都算不同路线。

输入格式

第一行输入 $H,W,K$。

接下来 $H$ 行输入方格图。

输出格式

输出长度为 K 的简单路线数量。

3 5 2
.....
..#..
....#

50

4 8 3
.....#.#
.......#
........
........

494

5 3 4
..#
#..
...
...
#..

136

数据范围与约定

• $1 \le H,W \le 10$
• $1 \le K \le 11$