Probability of Two Matching Strings in an Extended Matrix

Given an M × N matrix of letters, we create an infinite grid by repeating the matrix both horizontally and vertically. For example, if the matrix is:

honi
hsin

then the infinite grid is:

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

From this infinite grid, we perform the following process independently twice: randomly choose a starting cell (within one period of the matrix) and then read K consecutive letters moving to the right (wrapping around the period if necessary). This yields a string of length K. Compute the probability that the two strings obtained in this way are identical.

The answer should be represented as a reduced fraction P/Q.

Note: Since the infinite grid is periodic with period M rows and N columns, it suffices to consider the starting positions within the original matrix of size M×N.

inputFormat

The first line contains three integers M, N, and K (1 ≤ M, N, K ≤ 1000), representing the dimensions of the given letter matrix and the length of the string to be formed.

The following M lines each contain a string of N lowercase English letters, which represent the matrix.

outputFormat

Output the probability that the two strings are identical, expressed as a reduced fraction in the format P/Q (without spaces).

sample

2 4 2
honi
hsin

1/8