Description

You are given an $M \times N$ matrix of letters. For example:

honi
hsin

Then we extend it infinitely to get:

...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.

Input Format

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 Format

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

1 2 2
ab

5/16

2 4 3
honi
hsin

19/512

3 3 10
ban
ana
nab

2/27

Hint

【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 CONTEST #4.

The score of this problem follows the original COCI setting, with a full score of $160$.

Translated by ChatGPT 5