题目描述

有一块由 $H\times W$ 个单位方格组成的矩形场地。每个方格用一个字符表示：. 表示可通行但没有检查点，* 表示可通行且有一个检查点，# 表示障碍物，不能进入。

保证所有可通行方格（即 . 与 *）在四连通意义下构成一棵树：任意两个可通行方格之间恰好只有一条不重复经过方格的简单路径。

设场地中共有 $N$ 个检查点。现在从这 $N$ 个检查点中等概率随机选出恰好 $K$ 个。你需要找到一条最短的移动序列，使得它经过所有被选中的检查点。序列可以从任意方格开始，在任意方格结束；同一个方格允许被多次经过；每一步只能移动到共享一条边的相邻可通行方格。

序列的长度定义为移动次数。求最短序列长度的期望值。

输入格式

第一行三个整数 $H,W,K$。

接下来 $H$ 行，每行一个长度为 $W$ 的字符串，描述场地。

输出格式

输出一个实数，表示答案。

若你的答案与标准答案的绝对误差或相对误差不超过 $10^{-9}$，则认为正确。

数据范围

$1\le H,W\le 50$，$2\le K\le 300$；字符仅可能为 .,*,#；所有可通行方格构成四连通树；检查点数量在 $[K,300]$ 内。

样例

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

3.8333333333333353