Problem Description

Given an $M \times N$ letter matrix, for example:

honi
hsin

We then extend it infinitely, resulting in:

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

After the infinite extension, we randomly select a region of letters and then read $K$ consecutive letters in a certain direction. After performing this operation independently twice, we obtain two strings of length $K$. Calculate the probability that the two strings are identical.

Input Format

The first line contains three integers $N, M, K$.

The next $M$ lines each contain $N$ lowercase letters. Each line is guaranteed to have at least two distinct letters.

Output Format

Output the final probability in the simplest fraction form $\texttt{p/q}$.

Sample Input and Output

Sample Input #1

1 2 2
ab

Sample Output #1

5/16

Sample Input #2

2 4 3
honi
hsin

Sample Output #2

19/512

Sample Input #3

3 3 10
ban
ana
nab

Sample Output #3

2/27

Notes

[Data Range and Constraints]

For $100$ points of data, $M = N$.

For $100\%$ of the data, $1 \le M, N \le 500$, $2 \le K \le 10^9$.

[Hint and Attribution]

This problem is translated from COCI 2016-2017 CONTEST #4 T6 Osmosmjerka.

The score for this problem is set according to the original COCI problem, with a maximum score of $160$.

见题面 Input 部分

见题面 Output 部分