该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

强哥最近迷上了在小区里玩捉迷藏。小区可以看作是一个 $H \times W$ 的网格，每个格子代表一栋房子。设 $(i, j)$ 表示第 $i$ 行第 $j$ 列的房子。

有些房子是安全的（用 . 表示），强哥可以躲进去；有些房子有保安巡逻（用 # 表示），强哥不能进入。强哥决定从一个安全的房子开始，在小区里溜达 $K$ 步，每次只能移动到相邻的上、下、左、右的房子，并且不能重复进入同一栋房子（否则会被保安发现）。

请你计算强哥有多少种不同的溜达方式，既能躲开保安，又能不留下重复的脚印。

（只要有一步不同，就属于不同的溜达方式）

数据范围

输入格式

输入通过标准输入，格式如下。

$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}$

输出格式

2 2 2
.#
..

2

2 3 1
.#.
#.#

0