P7538 [COCI 2016/2017 #4] Osmosmjerka / [BJWC2018] Eight Dimensions.

You are given an $M \times N$ matrix of letters. For example: ```plain honi hsin ``` Then we extend it infinitely to get: ```plain ...honihonihonihoni... ...hsinhsinhsinhsin... ...honihonihonihoni... ...hsinhsinhsinhsin... ``` After obtaining the new matrix by infinite extension, we randomly choose a position in it, and then read $K$ consecutive letters along a fixed direction (8-connected). After independently performing the above process twice, we obtain two strings of length $K$. Find the probability that the two strings are the same.

The first line contains three integers $N, M, K$. The next $M$ lines each contain $N$ lowercase letters. It is guaranteed that each row has at least two different letters.

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

**【Constraints】** For the $100$-point testdata, $M = N$. For $100\%$ of the testdata, $1 \le M, N \le 500$, $2 \le K \le 10^9$. **【Hint and Notes】** **This problem is translated from _T6 Osmosmjerka_ of [COCI 2016-2017](https://hsin.hr/coci/archive/2016_2017/) [CONTEST #4](https://hsin.hr/coci/archive/2016_2017/contest4_tasks.pdf).** **The score of this problem follows the original COCI setting, with a full score of $160$.** Translated by ChatGPT 5