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

honi

hsin

可以无限复制出矩阵

...honihonihonihoni...

...hsinhsinhsinhsin...

...honihonihonihoni...

...hsinhsinhsinhsin...

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

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

例如，输入

122

ab

则输出

5/16

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

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

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

【样例解释】 
样例一中，一次操作共有 16 种可能，其中得到 aa 的概率是 1/8，得到 ab 的
概率是 3/8，得到 bb 的概率是 1/8，得到 ba 的概率是 3/8。两次操作结果相同的
概率是 5/16。 
【数据规模和约定】 
30%的测试数据：M, N ≤ 10，K ≤ 100。
50%的测试数据：M = N。 
100%的测试数据：1 ≤ M, N ≤ 500，2 ≤ K ≤ 109。

BJWC2018day1 NOIP高级