Probability of Repeated Strings in an Infinite Tiled Matrix

Consider an M × N character matrix. This matrix is tiled infinitely in all directions to form an infinite matrix. For example, given the matrix

honi
hsin

we can create an infinite matrix:

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

In the infinite matrix, we consider eight-connected connectivity, meaning that every position is adjacent to the positions above, below, left, right, and the four diagonal neighbors. Starting from any position one can move in one of these eight directions indefinitely.

A process is defined as follows: randomly select a starting position (each position in the period is equally likely) and then randomly select one of the eight directions (each with equal probability). From that starting position, read off K consecutive characters along the chosen direction (wrapping around as necessary due to the infinite tiling). Two independent processes are performed in this manner. Your task is to compute the probability that the two resulting strings are identical.

The string produced from a starting cell (i, j) and a direction (dr, dc) is given by:

\[ S = \bigl\{A_{(i + t \cdot dr) \bmod M,\, (j + t \cdot dc) \bmod N} : t = 0, 1, \ldots, K-1\bigr\} \]

where the original matrix is denoted by \(A\). The total number of distinct choices is \(8MN\) and if a particular string \(s\) is produced by \(f(s)\) choices then its probability is \(\frac{f(s)}{8MN}\). Hence, the required probability is:

\[ P = \sum_{s} \left(\frac{f(s)}{8MN}\right)^2 \]

You should output the answer as a reduced fraction \(P/Q\) (with no common divisors between \(P\) and \(Q\)).

inputFormat

The first line contains three integers M, N and K \((1 \le M, N \le 50,\, 1 \le K \le 50)\), representing the dimensions of the matrix and the length of the string to be formed.

The following M lines each contain a string of length N consisting of visible ASCII characters, representing the matrix.

outputFormat

Output a single reduced fraction in the format P/Q which represents the probability that two independently chosen strings are identical.

sample

1 1 3
a

1/1