题目描述

我们将一个 $M$ 行 $N$ 列的字符矩阵无限复制，可以得到一个无限字符矩阵。例如，对于以下矩阵:

$$\begin{aligned} & \verb!honi! \\ & \verb!hsin! \\ \end{aligned}$$

可以无限复制出矩阵

$$\begin{aligned} & \verb!...honihonihonihoni...! \\ & \verb!...hsinhsinhsinhsin...! \\ & \verb!...honihonihonihoni...! \\ & \verb!...hsinhsinhsinhsin...! \\ \end{aligned}$$

我们认为矩阵是八连通的。八连通， 指矩阵中的每个位置与上下左右和四个斜向（左上、右上、左下、右下）的位置相邻。因此，从矩阵任意位置出发沿八个方向中的任意一个都可以无限延长。

如果我们随机选择一个位置和一个方向，则可以从此位置开始沿此方向连续选取 $K$ 个字符组成一个字符串。问，两次这样操作得到两个相同字符串的概率是多少。(假设随机选择时任意位置是等可能的，任意方向也是等可能的)

输入格式

第一行是三个整数 $M, N, K$。

接下来 $M$ 行， 每行一个由小写英文字母组成的长度为 $N$ 的字符串，即 $M\times N$ 的字符矩阵。保证矩阵中至少出现两种不同字符。

输出格式

输出一行，为一个化简后的分数，表示概率。

1 2 2
ab

5/16

3 3 10
ban
ana
nab

2/27

提示

【样例解释】

样例一中，一次操作共有 $16$ 种可能，其中得到 $\verb!aa!$ 的概率是 $1/8$，得到 $\verb!ab!$ 的概率是 $3/8$,得到bb 的概率是 $1/8$，得到 $\verb!ba!$ 的概率是 $\verb!3/8!$。两次操作结果相同的 概率是 $5/16$。

【数据规模和约定】

• 对于 $30\%$ 的测试数据：$M, N ≤ 10$，$K ≤ 100$。
• 对于 $50\%$ 的测试数据：$M = N$。
• 对于 $100\%$ 的测试数据 ：$1 ≤ M,N ≤ 500$，$2 ≤ K ≤ 10^9$。