Description

We infinitely tile a character matrix with $M$ rows and $N$ columns to obtain an infinite character matrix. For example, for the following matrix:

$$\begin{aligned} & \verb!honi! \\ & \verb!hsin! \\ \end{aligned}$$

we can tile it infinitely to get

$$\begin{aligned} & \verb!...honihonihonihoni...! \\ & \verb!...hsinhsinhsinhsin...! \\ & \verb!...honihonihonihoni...! \\ & \verb!...hsinhsinhsinhsin...! \\ \end{aligned}$$

We consider the matrix to be 8-connected. 8-connected means each position in the matrix is adjacent to the positions above, below, left, right, and the four diagonals (upper-left, upper-right, lower-left, lower-right). Therefore, starting from any position in the matrix, you can extend infinitely along any one of the eight directions.

If we uniformly at random choose one position and one direction, then starting from this position and going along this direction, we take $K$ consecutive characters to form a string. What is the probability that two such operations produce identical strings? (Assume any position is equally likely and any direction is equally likely.)

Input Format

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

The next $M$ lines each contain a string of length $N$ consisting of lowercase English letters, forming the $M \times N$ character matrix. It is guaranteed that at least two different characters appear in the matrix.

Output Format

Output one line containing a reduced fraction representing the probability.

1 2 2
ab

5/16

3 3 10
ban
ana
nab

2/27

Hint

【Sample Explanation】

In Sample 1, there are $16$ possibilities for one operation in total. The probability of obtaining \verb!aa! is $1/8$, the probability of obtaining \verb!ab! is $3/8$, the probability of obtaining \verb!bb! is $1/8$, and the probability of obtaining \verb!ba! is $3/8$. The probability that the results of two operations are the same is $5/16$.

【Constraints】

• For $30\%$ of the testdata: $M, N \le 10$, $K \le 100$.
• For $50\%$ of the testdata: $M = N$.
• For $100\%$ of the testdata: $1 \le M, N \le 500$, $2 \le K \le 10^9$.

Translated by ChatGPT 5