4792: [BJWC2018] 八维

Memory Limit:256 MB Time Limit:15.000 S
Judge Style:Text Compare Creator:
Submit:1 Solved:1

Description

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

honihsin

可以无限复制出矩阵

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

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

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

Input

第一行是三个整数 ,,

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

Output

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

Sample Input Copy

3 3 10
ban
ana
nab

Sample Output Copy

2/27

HINT

【样例解释】 

样例一中,一次操作共有 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