시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
4 초 | 256 MB | 16 | 8 | 5 | 62.500% |
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.
The first line of input contains integers M, N, K from the task (1 ≤ M, N ≤ 500, 2 ≤ K ≤ 109 ).
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
5/16
2 4 3 honi hsin
19/512
3 3 10 ban ana nab
2/27