题目描述

给定一个 $M \times N$ 的字母矩阵，以下面的为例：

honi
hsin

接着我们将其进行无限延伸，得到：

...honihonihonihoni...
...hsinhsinhsinhsin...
...honihonihonihoni...
...hsinhsinhsinhsin...

在无限延伸后得到的新矩阵后，我们随机选取其中一个区域的字母，然后再沿着一定的方向连续读取 $K$ 个字母。在独立完成上述操作两次之后，我们会得到两个长度为 $K$ 的字符串。求两个字符串相同的概率。

输入格式

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

接下来的 $M$ 行，每行 $N$ 个小写字母。保证每行至少有两个不同的字母。

输出格式

以最简分数 $\texttt{p/q}$ 的形式输出最终概率。

1 2 2
ab

5/16

2 4 3
honi
hsin

19/512

3 3 10
ban
ana
nab

2/27

提示

【数据规模与约定】

对于其中 $100$ 分的数据，$M=N$。

对于 $100\%$ 的数据，$1 \le M,N \le 500$，$2 \le K \le 10^9$。

【提示与说明】

题目译自 COCI 2016-2017 CONTEST #4 T6 Osmosmjerka。

本题分值按 COCI 原题设置，满分 $160$。