레이팅 미적용4 \(s / 256\) \(MB / 160\) points
We have created an infinite eight-directional crossword by taking a letter-filled block of
dimensions \(M\)
x \(N\)
and infinitely repeating it. For instance, if we are given the following block:
honi
hsin
then we create the following crossword:
...honihonihonihoni...
...hsinhsinhsinhsin...
...honihonihonihoni...
...hsinhsinhsinhsin...
that is inifinite in all directions.
In the created crossword, we randomly choose a field and one of eight directions, then write
down a word of length \(K\) obtained by reading the crossword starting from the initial field, in
the chosen direction. If we executed this query twice (independently), we would obtain two
words of length \(K\)
. Calculate the probability that the two words are equal.
In test cases worth 100 total points, it will hold \(M\)
= \(N\)
.
The first line of input contains integers M,
N, K
from the task (1 ≤ M, N
≤ 500, 2 ≤ \(K\)
≤ 10 {9}{ }).
Each of the following \(M\)
lines contains \(N\)
lowercase letters of the English alphabet, and
describes a block of the crossword. At least two distinct letters will exist in the block.
You must output the required probability in the form of a reduced fraction \(p/q\),
without
spaces.
1 2 2
ab
2 4 3
honi
hsin
3 3 10
ban
ana
naboutput
output
4 s / 256 MB / 160 points
5/16
19/512
2/27